Euclidean minimum spanning trees and bichromatic closest pairs
From MaRDI portal
Publication:1176318
DOI10.1007/BF02574698zbMath0753.68089WikidataQ54310199 ScholiaQ54310199MaRDI QIDQ1176318
Herbert Edelsbrunner, Pankaj K. Agarwal, Otfried Schwarzkopf, Ermo Welzl
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131167
68Q25: Analysis of algorithms and problem complexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W10: Parallel algorithms in computer science
Related Items
Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\), Diameter, width, closest line pair, and parametric searching, On ray shooting in convex polytopes, On the symmetric angle-restricted nearest neighbor problem, Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric, Planar bichromatic minimum spanning trees, Cutting hyperplane arrangements, Euclidean minimum spanning trees and bichromatic closest pairs, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Dynamic point location in arrangements of hyperplanes, Relative neighborhood graphs in three dimensions, On the Steiner ratio in 3-space, Dynamic Euclidean minimum spanning trees and extrema of binary functions, Dynamic half-space range reporting and its applications, Computing depth orders for fat objects and related problems, Average case analysis of dynamic geometric optimization
Cites Work
- Combinatorial complexity bounds for arrangements of curves and spheres
- Euclidean minimum spanning trees and bichromatic closest pairs
- Applications of random sampling in computational geometry. II
- A randomized algorithm for fixed-dimensional linear programming
- How to search in history
- Optimal Point Location in a Monotone Subdivision
- A Randomized Algorithm for Closest-Point Queries
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item