---
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 K
foaf_surname: Agarwal
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
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_publisher: Springer@
dct_title: Euclidean minimum spanning trees and bichromatic closest pairs@
...