Author(s):

Aggarwal, Alok; Edelsbrunner, Herbert; Raghavan, Prabhakar; Tiwari, Prasoon

Article Title: 
Optimal time bounds for some proximity problems in the plane

Affiliation 

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 wellknown 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:

00200190

Publisher:

Elsevier

Date Published:

19920427

Start Page: 
55

End Page:

60

DOI: 
10.1016/00200190(92)90133G

Open access: 
no 