×

Euclidean minimum spanning trees and bichromatic closest pairs. (English) Zbl 0753.68089

The important problem of the efficient computation of Euclidean minimum spanning trees on \(N\) points in a fixed dimension space \(E^ d\) is considered. The authors develop \(O(T_ d(N,N)\log^ d N)\) algorithm, \(T_ d(n,m)\) is the time needed for the computation of bichromatic closest pair of \(n\) blue and \(m\) red points in \(E^ d\).
Furthermore for \(d=3\) a fast randomized \(O(N^{4/3}\log^{4/3} N)\) algorithm is described.
In my opinion the results, the analysis and the randomization technique are new and turn to be an essential tool for researches in computational geometry.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] [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. · Zbl 0753.68089
[2] [AM] P. K. Agarwal and J. Matoušek, Personal communication.
[3] [Ch] B. Chazelle, How to search in history,Information and Control64 (1985), 77-99. · Zbl 0575.68062
[4] [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.
[5] [CEG+] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres,Discrete & Computational Geometry5 (1990), 99-160. · Zbl 0704.51003
[6] [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.
[7] [C12] K. Clarkson, A randomized algorithm for closest-point queries,SIAM Journal on Computing17 (1988), 830-847. · Zbl 0651.68062
[8] [CS] K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II.Discrete & Computational Geometry4 (1989), 387-422. · Zbl 0681.68060
[9] [DF] M. E. Dyer and A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming,Mathematical Programming44 (1989), 203-212. · Zbl 0681.90054
[10] [E] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001
[11] [EGS] H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM Journal on Computing15 (1986), 317-340. · Zbl 0602.68102
[12] [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.
[13] [M] S. Meiser, Suche in einem Arrangement von Hyperebenen, Diplomarbeit, Universität des Saarlandes, 1988.
[14] [PS] F. Preparata and M. Shamos,Computational Geometry—An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037
[15] Preparata, F.; Tamassia, R., Efficient spatial point location, No. Vol. 382, 3-11 (1989), Berlin · Zbl 0794.68025
[16] [ST] N. Sarnak and R. Tarjan, Planar point location using persistent search trees,Communications of the ACM29 (1986), 669-679.
[17] [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.
[18] [S2] R. Seidel, Linear programming and convex hulls made easy,Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1900, pp. 211-215.
[19] [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.
[20] [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.
[21] [Y] A. Yao, On constructing minimum spanning trees ink-dimensional spaces and related problems,SIAM Journal on Computing11 (1982), 721-736. · Zbl 0492.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.