Euclidean minimum spanning trees and bichromatic closest pairs |
| |
Authors: | Pankaj K Agarwal Herbert Edelsbrunner Otfried Schwarzkopf Emo Welzl |
| |
Institution: | 1. Department of Computer Science, Duke University, 27706, Durham, NC, USA 2. Department of Computer Science, University of Illinois at, Urbana-Champaign, 61801, Urbana, IL, USA 3. Institut für Informatik, Fachbereich Mathematik, Freie Universit?t Berlin, Arnimallee 2-6, 1000, Berlin 33, Federal Republic of Germany
|
| |
Abstract: | We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE
d
in timeO(F
d
(N,N) log
d
N), whereF
d
(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE
d
. IfF
d
(N,N)=Ω(N
1+ε), for some fixed ɛ>0, then the running time improves toO(F
d
(N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)2/3+m log2
n+n log2
m) inE
3, which yields anO(N
4/3 log4/3
N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE
3. Ind≥4 dimensions we obtain expected timeO((nm)1−1/(d/2]+1)+ε+m logn+n logm) for the bichromatic closest pair problem andO(N
2−2/(d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive ɛ.
The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer
Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's
work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the
Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”.
The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No.
3075 (project ALCOM). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|