On the Spanning Ratio of Gabriel Graphs and beta-Skeletons

DOI10.1137/S0895480197318088MaRDI QIDQ3440264zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Luc Devroye, W. Evans, David 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

computational geometryprobabilistic analysisGabriel graphspannersgeometric spanners\(\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)

Recommendations

• scientific article; zbMATH DE number 2086250
• Optimal and suboptimal robust algorithms for proximity graphs
• scientific article; zbMATH DE number 1830717
• Some properties of k-Delaunay and k-Gabriel graphs
• \(\beta\)-skeletons for a set of line segments in \(\mathbb R^2\)

Cited in

(17)

• scientific article; zbMATH DE number 2086250 (Why is no real title available?)
• Characterizing proximity trees
• Proximity structures for geometric graphs
• Empty region graphs
• On a family of strong geometric spanners that admit local routing strategies
• Efficient Computation of Elliptic Gabriel Graph
• Hardness results for computing optimal locally Gabriel graphs
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
• On growing connected \(\beta \)-skeletons
• On plane geometric spanners: a survey and open problems
• (1 + εΒ) -spanner constructions for general graphs
• 10-Gabriel graphs are Hamiltonian
• Sigma-local graphs
• Distribution-sensitive construction of the greedy spanner
• On the expected maximum degree of Gabriel and Yao graphs
• The \(\gamma\)-neighborhood graph
• Connected spatial networks over random points and a route-length statistic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3440264)