Dynamic planar nearest neighbors in logarithmic time
A nearest-neighbor query on a set of points in the plane asks, for a query point, for a point of the set closest to it in Euclidean distance. It suffices to solve a three-dimensional problem: keep the convex hull of $n$ points in $\mathbb{R}^3$ up to date as points are added and removed, while answering extreme-point queries. On the line, balanced search trees support all three operations in $O(\log n)$ time.
Agarwal and Matoušek gave two structures, one with $O(n^\varepsilon)$ amortized updates and $O(\log n)$ worst-case queries, the other with $O(\log^2 n)$ amortized updates and $O(n^\varepsilon)$ worst-case queries, for any $\varepsilon > 0$. Without deletions, the Bentley–Saxe method for decomposable search problems gives $O(\log^2 n)$ amortized time for updates and queries. Chan obtained the first polylogarithmic structure: insertions in $O(\log^3 n)$ and deletions in $O(\log^6 n)$ expected amortized time, and queries in $O(\log^2 n)$ worst-case time.
Problem. Is there a data structure that maintains a set of $n$ points in the plane under insertions, deletions and nearest-neighbor queries, each in $O(\log n)$ time?
Source: Origin uncertain; Problem 63 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Keywords
- data structures, dynamic convex hull, dynamic nearest neighbor, The Open Problems Project
References
@article{agarwal1995,
author = {Agarwal, P. K. and Matou{\v{s}}ek, J.},
title = {Dynamic half-space range reporting and its applications},
journal = {Algorithmica},
volume = {13},
year = {1995},
pages = {325--345},
}
@article{bentley1980,
author = {Bentley, J. L. and Saxe, J. B.},
title = {Decomposable searching problems {I}: Static-to-dynamic transformations},
journal = {J. Algorithms},
volume = {1},
year = {1980},
pages = {301--358},
}
@inproceedings{chan2006,
author = {Chan, Timothy},
title = {A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries},
booktitle = {Proc. 17th ACM-SIAM Symposium on Discrete Algorithms},
year = {2006},
pages = {1196--1202},
url = {https://dl.acm.org/doi/10.5555/1109557.1109689},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01101, "Dynamic planar nearest neighbors in logarithmic time", clopen.solutions.