Next: Problem 64: Edge-Unfolding Polycubes
Previous: Problem 62: Volume Maximizing Convex Shape
Is there a data structure maintaining a set of n points in the plane subject to insertions, deletions, and nearest-neighbor queries in O(\log n) 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 n points in 3D subject to insertions, deletions, and extreme-point queries.
Uncertain, pending investigation.
Open.
This problem is the natural generalization of (1D) search trees to 2D. Standard balanced search tree data structures can maintain n points on the real line subject to insertion, deletion, and predecessor and successor queries (and thus nearest-neighbor queries) in O(\log n) time per operation. (More sophisticated data structures even attain O(1) time per update.)
For 14 years, the authority on this problem was Agarwal and Matoušek’s FOCS’92 paper [AM95] which describes two data structures: one suports updates in O(n^\epsilon) amortized time and queries in O(\log n) worst-case time, while the other suports updates in O(\log^2 n) amortized time queries in O(n^\epsilon) worst-case time, for any \epsilon > 0. The nearest-neighbor problem is a decomposable search problem, so when deletions are forbidden, the general techniques of Bentley and Saxe [BS80] yield an O(\log^2 n) amortized bound for updates and queries. In 2006, Chan [Cha06] obtained the first polylogarithimc data structure for 3D convex hulls and therefore 2D nearest neighbors. His data structure supports insertions in O(\log^3 n) expected amortized time, deletions in O(\log^6 n) expected amortized time, and extreme-point or nearest-neighbor queries in O(\log^2 n) worst-case time.
convex hulls; data structures; Voronoi diagrams
E. Demaine, 24 Jan. 2006.
P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications. Algorithmica, 13:325–345, 1995.
J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformations. J. Algorithms, 1:301–358, 1980.
Timothy Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 1196–1202, 2006.