A sparse graph almost as good as the complete graph on points in \(k\) dimensions
From MaRDI portal
Publication:1814131
DOI10.1007/BF02574695zbMath0755.05059MaRDI QIDQ1814131
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131164
Related Items (23)
Efficient construction of a bounded-degree spanner with low weight ⋮ Euclidean spanner graphs with degree four ⋮ Spanners of de Bruijn and Kautz graphs ⋮ Balancing minimum spanning trees and shortest-path trees ⋮ On bounded leg shortest paths problems ⋮ Unnamed Item ⋮ An Optimal Dynamic Spanner for Doubling Metric Spaces ⋮ Sparse geometric graphs with small dilation ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ Computing a minimum-dilation spanning tree is NP-hard ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ Well-separated pair decomposition in linear time? ⋮ Lower bounds for computing geometric spanners and approximate shortest paths ⋮ MIXED SPANNING TREES IN THEORY AND PRACTICE ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Spanners of Complete k-Partite Geometric Graphs ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ Unnamed Item ⋮ Region-fault tolerant geometric spanners ⋮ Fully dynamic geometric spanners ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Average stretch factor: how low does it go? ⋮ Approximating Euclidean distances by small degree graphs
Cites Work
- Delaunay graphs are almost as good as complete graphs
- An O(n log n) algorithm for the all-nearest-neighbors problem
- Quad trees: A data structure for retrieval by composite keys
- Approximate minimum weight matching on points in k-dimensional space
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Unnamed Item
- Unnamed Item
This page was built for publication: A sparse graph almost as good as the complete graph on points in \(k\) dimensions
