Next: Problem 64: EdgeUnfolding 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 nearestneighbor queries in O(log n) time?
A nearestneighbor 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 extremepoint 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 nearestneighbor 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) worstcase time,
while the other suports updates in
O(log^{2}n) amortized time
queries in
O(n^{ε}) worstcase time,
for any
ε > 0.
The nearestneighbor 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 extremepoint or nearestneighbor queries in
O(log^{2}n)
worstcase time.
 Related Open Problems
 Problem 12.
 Categories
 convex hulls; data structures; Voronoi diagrams
 Entry Revision History
 E. Demaine, 24 Jan. 2006.
 AM95

P. K. Agarwal and J. Matoušek.
Dynamic halfspace range reporting and its applications.
Algorithmica, 13:325345, 1995.
 BS80

J. L. Bentley and J. B. Saxe.
Decomposable searching problems I: Statictodynamic
transformations.
J. Algorithms, 1:301358, 1980.
 Cha06

Timothy Chan.
A dynamic data structure for 3d convex hulls and
2d nearest neighbor
queries.
In Proceedings of the 17th ACMSIAM Symposium on Discrete
Algorithms, 2006.
to appear.
Next: Problem 64: EdgeUnfolding Polycubes
Up: The Open Problems Project
Previous: Problem 62: Volume Maximizing
The Open Problems Project  December 08, 2012