TY - JOUR
AB - Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.
AU - Aggarwal, Alok
AU - Herbert Edelsbrunner
AU - Raghavan, Prabhakar
AU - Tiwari, Prasoon
ID - 4048
IS - 1
JF - Information Processing Letters
TI - Optimal time bounds for some proximity problems in the plane
VL - 42
ER -