Farthest neighbors, maximum spanning trees and related problems in higher dimensions
From MaRDI portal
Publication:1194310
DOI10.1016/0925-7721(92)90001-9zbMath0769.68037OpenAlexW2158944832WikidataQ127212875 ScholiaQ127212875MaRDI QIDQ1194310
Pankaj K. Agarwal, Subhash Suri, Ji{ří} Matoušek
Publication date: 27 September 1992
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0925-7721(92)90001-9
randomized algorithmtime complexityapproximation algorithmsmaximum spanning treefarthest neighbors\(k\)-dimensional space
Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)
Related Items
APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, Packing two disks into a polygonal environment., Communication costs in a geometric communication network, Finding Largest Well-Predicted Subset of Protein Structure Models, Computing farthest neighbors on a convex polytope., Unnamed Item, An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions, Group nearest-neighbor queries in the \(L_1\) plane, Relative neighborhood graphs in three dimensions, An almost space-optimal streaming algorithm for coresets in fixed dimensions, Farthest-point queries with geometric and combinatorial constraints, Faster core-set constructions and data-stream algorithms in fixed dimensions, GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS, On the longest spanning tree with neighborhoods, Streaming algorithms for extent problems in high dimensions, On Some Proximity Problems of Colored Sets, Computing Euclidean bottleneck matchings in higher dimensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- An acyclicity theorem for cell complexes in d dimensions
- Computing Euclidean maximum spanning trees
- A linear-time algorithm for a special case of disjoint set union
- Voronoi diagrams and arrangements
- \(\epsilon\)-nets and simplex range queries
- An O(n log n) algorithm for the all-nearest-neighbors problem
- Approximating the diameter of a set of points in the Euclidean space
- Euclidean minimum spanning trees and bichromatic closest pairs
- Applications of random sampling in computational geometry. II
- How to search in history
- Improved algorithms for discs and balls using power diagrams
- A Randomized Algorithm for Closest-Point Queries
- Minimum Spanning Trees in k-Dimensional Space
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- On the History of the Minimum Spanning Tree Problem
