---
res:
  bibo_abstract:
  - We present an algorithm to compute a Euclidean minimum spanning tree of a given
    set S of N points in Ed in time O(Fd (N,N) logd N), where Fd (n,m) is the time
    required to compute a bichromatic closest pair among n red and m green points
    in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}>0, then the running time
    improves to O(Fd (N,N)). Furthermore, we describe a randomized algorithm to compute
    a bichromatic closest pair in expected time O((nm log n log m)2/3+m log2 n+n log2
    m) in E3, which yields an O(N4/3 log4/3 N) expected time, algorithm for computing
    a Euclidean minimum spanning tree of N points in E3. In d≥4 dimensions we obtain
    expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest
    pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem,
    for any positive e{open}.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Pankaj
      foaf_name: Agarwal, Pankaj
      foaf_surname: Agarwal
  - 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: Otfried
      foaf_name: Schwarzkopf, Otfried
      foaf_surname: Schwarzkopf
  - foaf_Person:
      foaf_givenName: Emo
      foaf_name: Welzl, Emo
      foaf_surname: Welzl
  bibo_doi: 10.1007/BF02574698
  bibo_issue: '1'
  bibo_volume: 6
  dct_date: 1991^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0179-5376
  - http://id.crossref.org/issn/1432-0444
  dct_language: eng
  dct_publisher: Springer@
  dct_title: Euclidean minimum spanning trees and bichromatic closest pairs@
...