← All problems
Dynamic Planar Nearest Neighbors
Is there a data structure maintaining a set of points in the plane subject to insertions, deletions, and nearest-neighbor queries in time? A nearest-neighbor query asks to find a point among the set that is nearest (in Euclidean distance) to a given a point in the plane. This problem reduces to maintaining the convex hull of a set of points in 3D subject to insertions, deletions, and extreme-point queries.
