Geometry
Notes
When comparing euclidean distance between two pairs of points, using dx2 + dy2 is sufficient. It is unnecessary to square root the value.
To find out if two circles overlap, check that the distance between the two centers of the circles is less than the sum of their radii.
Sample questions
- You have a plane with lots of rectangles on it, find out how many of them intersect.
- Which data structure would you use to query the k-nearest points of a set on a 2D plane?
- Given many points, find k points that are closest to the origin.
- How would you triangulate a polygon?