Euclidean minimum spanning trees and bichromatic closest pairs
From MaRDI portal
Publication:1176318
DOI10.1007/BF02574698zbMath0753.68089WikidataQ54310199 ScholiaQ54310199MaRDI QIDQ1176318
Pankaj K. Agarwal, Otfried Schwarzkopf, Herbert Edelsbrunner, 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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items
Kinetic \(k\)-semi-Yao graph and its applications ⋮ On the symmetric angle-restricted nearest neighbor problem ⋮ Bottleneck bichromatic full Steiner trees ⋮ Dynamic half-space range reporting and its applications ⋮ On the Steiner ratio in 3-space ⋮ Dynamic Euclidean minimum spanning trees and extrema of binary functions ⋮ Plane bichromatic trees of low degree ⋮ A new approach for the multiobjective minimum spanning tree ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ An Approximation Algorithm for the Smallest Color-Spanning Circle Problem ⋮ Computing depth orders for fat objects and related problems ⋮ Average case analysis of dynamic geometric optimization ⋮ Dynamic connectivity in disk graphs ⋮ Colored spanning graphs for set visualization ⋮ Minimizing interference in ad hoc networks with bounded communication radius ⋮ Cutting hyperplane arrangements ⋮ Euclidean minimum spanning trees and bichromatic closest pairs ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ Diameter, width, closest line pair, and parametric searching ⋮ On ray shooting in convex polytopes ⋮ Dynamic point location in arrangements of hyperplanes ⋮ Relative neighborhood graphs in three dimensions ⋮ Connected dominating sets on dynamic geometric graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\) ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces ⋮ Unnamed Item ⋮ Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric ⋮ Planar bichromatic minimum spanning trees ⋮ On Some Proximity Problems of Colored Sets ⋮ Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
