next up previous
Next: Problem 64: Edge-Unfolding Polycubes Up: The Open Problems Project Previous: Problem 62: Volume Maximizing


Problem 63: Dynamic Planar Nearest Neighbors

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ε) amortized time and queries in O(log n) worst-case time, while the other suports updates in O(log2n) amortized time queries in O(nε) worst-case time, for any ε > 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(log2n) 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(log3n) expected amortized time, deletions in O(log6n) expected amortized time, and extreme-point or nearest-neighbor queries in O(log2n) worst-case time.
Related Open Problems
Problem 12.
Categories
convex hulls; data structures; Voronoi diagrams
Entry Revision History
E. Demaine, 24 Jan. 2006.

Bibliography

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.


next up previous
Next: Problem 64: Edge-Unfolding Polycubes Up: The Open Problems Project Previous: Problem 62: Volume Maximizing
The Open Problems Project - December 08, 2012