**Next:** Problem 64: Edge-Unfolding Polycubes

**Previous:** Problem 62: Volume Maximizing Convex Shape

- Statement
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.- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- Motivation
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.)

- Partial and Related Results
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.

- Related Open Problems
- Categories
convex hulls; data structures; Voronoi diagrams

- Entry Revision History
E. Demaine, 24 Jan. 2006.

- [AM95]
P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications.

*Algorithmica*, 13:325–345, 1995.- [BS80]
J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformations.

*J. Algorithms*, 1:301–358, 1980.- [Cha06]
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*, 2006. to appear.