@article{4048,
  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.},
  author       = {Aggarwal, Alok and Edelsbrunner, Herbert and Raghavan, Prabhakar and Tiwari, Prasoon},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {55 -- 60},
  publisher    = {Elsevier},
  title        = {{Optimal time bounds for some proximity problems in the plane}},
  doi          = {10.1016/0020-0190(92)90133-G},
  volume       = {42},
  year         = {1992},
}