← All problems

Dynamic Planar Nearest Neighbors

Is there a data structure maintaining a set of nn points in the plane subject to insertions, deletions, and nearest-neighbor queries in O(log⁡n)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 nn points in 3D subject to insertions, deletions, and extreme-point queries.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu