On the Spanning Ratio of Gabriel Graphs and beta-Skeletons

DOI10.1137/S0895480197318088zbMath1115.68107OpenAlexW2039111454MaRDI QIDQ3440264

Prosenjit Bose, William S. Evans, Luc P. Devroye, David G. Kirkpatrick

Publication date: 22 May 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480197318088

zbMATH Keywords

probabilistic analysisgeometric spannerscomputational geometryspannersGabriel graph\(\beta\)-skeletonsproximity graphs

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (10)

On plane geometric spanners: a survey and open problems ⋮ HARDNESS RESULTS FOR COMPUTING OPTIMAL LOCALLY GABRIEL GRAPHS ⋮ Connected spatial networks over random points and a route-length statistic ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ PROXIMITY STRUCTURES FOR GEOMETRIC GRAPHS ⋮ Sigma-local graphs ⋮ Empty region graphs ⋮ 10-Gabriel graphs are Hamiltonian

This page was built for publication: On the Spanning Ratio of Gabriel Graphs and beta-Skeletons