---
_id: '4048'
abstract:
- lang: eng
  text: '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.'
acknowledgement: Research supported by the National Science Foundation under Grant
  CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Alok
  full_name: Aggarwal, Alok
  last_name: Aggarwal
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Prabhakar
  full_name: Raghavan, Prabhakar
  last_name: Raghavan
- first_name: Prasoon
  full_name: Tiwari, Prasoon
  last_name: Tiwari
citation:
  ama: Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. Optimal time bounds for some
    proximity problems in the plane. <i>Information Processing Letters</i>. 1992;42(1):55-60.
    doi:<a href="https://doi.org/10.1016/0020-0190(92)90133-G">10.1016/0020-0190(92)90133-G</a>
  apa: Aggarwal, A., Edelsbrunner, H., Raghavan, P., &#38; Tiwari, P. (1992). Optimal
    time bounds for some proximity problems in the plane. <i>Information Processing
    Letters</i>. Elsevier. <a href="https://doi.org/10.1016/0020-0190(92)90133-G">https://doi.org/10.1016/0020-0190(92)90133-G</a>
  chicago: Aggarwal, Alok, Herbert Edelsbrunner, Prabhakar Raghavan, and Prasoon Tiwari.
    “Optimal Time Bounds for Some Proximity Problems in the Plane.” <i>Information
    Processing Letters</i>. Elsevier, 1992. <a href="https://doi.org/10.1016/0020-0190(92)90133-G">https://doi.org/10.1016/0020-0190(92)90133-G</a>.
  ieee: A. Aggarwal, H. Edelsbrunner, P. Raghavan, and P. Tiwari, “Optimal time bounds
    for some proximity problems in the plane,” <i>Information Processing Letters</i>,
    vol. 42, no. 1. Elsevier, pp. 55–60, 1992.
  ista: Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. 1992. Optimal time bounds
    for some proximity problems in the plane. Information Processing Letters. 42(1),
    55–60.
  mla: Aggarwal, Alok, et al. “Optimal Time Bounds for Some Proximity Problems in
    the Plane.” <i>Information Processing Letters</i>, vol. 42, no. 1, Elsevier, 1992,
    pp. 55–60, doi:<a href="https://doi.org/10.1016/0020-0190(92)90133-G">10.1016/0020-0190(92)90133-G</a>.
  short: A. Aggarwal, H. Edelsbrunner, P. Raghavan, P. Tiwari, Information Processing
    Letters 42 (1992) 55–60.
date_created: 2018-12-11T12:06:38Z
date_published: 1992-04-27T00:00:00Z
date_updated: 2022-03-16T09:20:13Z
day: '27'
doi: 10.1016/0020-0190(92)90133-G
extern: '1'
intvolume: '        42'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/002001909290133G
month: '04'
oa_version: None
page: 55 - 60
publication: Information Processing Letters
publication_identifier:
  eissn:
  - 1872-6119
  issn:
  - 0020-0190
publication_status: published
publisher: Elsevier
publist_id: '2080'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal time bounds for some proximity problems in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 42
year: '1992'
...