Geometry

• 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?