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) logd 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 ɛ.
Article PDF
Similar content being viewed by others
References
[AESW] P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Euclidean minimum spanning trees and bichromatic closest pairs,Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 203–210.
[AM] P. K. Agarwal and J. Matoušek, Personal communication.
[Ch] B. Chazelle, How to search in history,Information and Control 64 (1985), 77–99.
[CEGS] B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Algorithms for bichromatic line segment problems and polyhedral terrains, Report UIUCDCS-R-90-1578. Dept. Computer Science, Univ. Illinois. Urbana, 1990.
[CEG+] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres,Discrete & Computational Geometry 5 (1990), 99–160.
[C11] K. Clarkson, Fast expected-time and approximate algorithms for geometric minimum spanning tree,Proceedings of the 16th annual ACM Symposium on Theory of Computing, 1984, pp. 343–348.
[C12] K. Clarkson, A randomized algorithm for closest-point queries,SIAM Journal on Computing 17 (1988), 830–847.
[CS] K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II.Discrete & Computational Geometry 4 (1989), 387–422.
[DF] M. E. Dyer and A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming,Mathematical Programming 44 (1989), 203–212.
[E] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
[EGS] H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM Journal on Computing 15 (1986), 317–340.
[GBT] H. N. Gabow, J. L. Bentley and R. E. Tarjan, Scaling and related techniques for geometry problems,Proceedings of the 16th Annual ACM Symposium on theory of Computing, 1984, pp. 135–143.
[M] S. Meiser, Suche in einem Arrangement von Hyperebenen, Diplomarbeit, Universität des Saarlandes, 1988.
[PS] F. Preparata and M. Shamos,Computational Geometry—An Introduction, Springer-Verlag, New York, 1985.
[PT] F. Preparata and R. Tamassia, Efficient spatial point location.,Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 382. Springer-Verlag, Berlin, 1989, pp. 3–11.
[ST] N. Sarnak and R. Tarjan, Planar point location using persistent search trees,Communications of the ACM 29 (1986), 669–679.
[S1] R. Seidel, A convex hull algorithm optimal for point sets in even dimensions, Technical Report 81-14. Dept. Computer Science, Univ. British Columbia, Van couver, 1981.
[S2] R. Seidel, Linear programming and convex hulls made easy,Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1900, pp. 211–215.
[SH] M. Shamos and D. Hoey, Closest-point problems,Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, 1975, pp. 151–162.
[V] P. Vaidya, A fast approximate algorithm for the minimum spanning tree ink-dimensional space,Proceedings of the 25th Annual IEEE Symposium on Foundation of Computer Science, 1984, pp. 403–407.
[Y] A. Yao, On constructing minimum spanning trees ink-dimensional spaces and related problems,SIAM Journal on Computing 11 (1982), 721–736.
Author information
Authors and Affiliations
Additional information
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).
Rights and permissions
About this article
Cite this article
Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O. et al. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput Geom 6, 407–422 (1991). https://doi.org/10.1007/BF02574698
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574698