Optimal time bounds for some proximity problems in the plane Journal Article

Author(s): Aggarwal, Alok; Edelsbrunner, Herbert; Raghavan, Prabhakar; Tiwari, Prasoon
Article Title: Optimal time bounds for some proximity problems in the plane
Abstract: 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.
Keywords: computational geometry; point sets; upper and lower bounds; simple polygons; Euclidean distance; algebraic decision tree model; integer element uniqueness problem
Journal Title: Information Processing Letters
Volume: 42
Issue 1
ISSN: 0020-0190
Publisher: Elsevier  
Date Published: 1992-04-27
Start Page: 55
End Page: 60
DOI: 10.1016/0020-0190(92)90133-G
Open access: no
IST Austria Authors
Related IST Austria Work