Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires Ω(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. © 1992.
Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007