Dynamic Planar Nearest Neighbors
Let be a finite set of points, and write . The question is whether one can maintain under valid insertions and deletions and, for every query point when is nonempty, return a nearest point in ; ties may be resolved by returning any minimizer. In other words, the query must return some such that
The target is time for insertions, deletions, and queries, with denoting the current set size. The question states no restriction on the point coordinates or computational model. Open Problems Project, Problem 63
The stated reduction uses the paraboloid lifting . For a query , minimizing squared Euclidean distance is equivalent to maximizing a linear functional of the lifted point:
so a nearest neighbor corresponds to a point of the lifted set maximizing the direction . Thus the reduction is to dynamic extreme-point queries on the convex hull of the lifted points in . Open Problems Project, Problem 63 Chan (2010)
Background
Static planar nearest-neighbor search admits preprocessing and query time, but allowing both insertions and deletions makes the problem substantially harder. The comparison with one-dimensional search is instructive: balanced search trees support dynamic predecessor and successor, and hence nearest-neighbor, queries in logarithmic time. In the plane, the challenge is to maintain enough information about the changing Voronoi diagram—or, through the lifting above, the changing three-dimensional hull—without paying for extensive structural changes after updates. Chan (2010) Open Problems Project, Problem 63
Agarwal and Matoušek’s work on dynamic half-space range reporting and its applications established early general bounds for planar nearest neighbors. A different regime is easier: because nearest-neighbor search is decomposable, the Bentley–Saxe static-to-dynamic technique gives an amortized bound for updates and queries when deletions are forbidden. The fully dynamic problem instead requires handling arbitrary online sequences of insertions and deletions. Agarwal and Matoušek (1995) Bentley and Saxe (1980) Chan (2010)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.