---
res:
  bibo_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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Alok
      foaf_name: Aggarwal, Alok
      foaf_surname: Aggarwal
  - foaf_Person:
      foaf_givenName: Herbert
      foaf_name: Edelsbrunner, Herbert
      foaf_surname: Edelsbrunner
      foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9823-6833
  - foaf_Person:
      foaf_givenName: Prabhakar
      foaf_name: Raghavan, Prabhakar
      foaf_surname: Raghavan
  - foaf_Person:
      foaf_givenName: Prasoon
      foaf_name: Tiwari, Prasoon
      foaf_surname: Tiwari
  bibo_doi: 10.1016/0020-0190(92)90133-G
  bibo_issue: '1'
  bibo_volume: 42
  dct_date: 1992^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0020-0190
  - http://id.crossref.org/issn/1872-6119
  dct_language: eng
  dct_publisher: Elsevier@
  dct_title: Optimal time bounds for some proximity problems in the plane@
...