2006/01/01 by Prosenjit Bose, Luc Devroye, William Evans +1 · 84 citations
Computer Science · Environmental Science · Mathematics · #Computational Geometry and Mesh Generation #Remote Sensing and LiDAR Applications #Data Management and Algorithms #Combinatorics #Mathematics #Spanner #Spanning tree #Euclidean geometry #Graph #BETA (programming language) #Discrete mathematics #Geometry #Computer science
paper · doi:10.1137/s0895480197318088
published in SIAM Journal on Discrete Mathematics 20(2), 412-427 (Society for Industrial and Applied Mathematics)
openalex publication_date 2006/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio over all pairs of data points (u,v) of the minimum graph distance between u and v divided by the Euclidean distance between u and v. A connected graph is said to be an S-spanner if the spanning ratio does not exceed S. For example, for any S there exists a point set whose minimum spanning tree isnot an S-spanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42-spanner [J. M. Keil and C. A. Gutwin, Discrete Comput. Geom., 7 (1992), pp. 13-28]. For proximity graphs between these two extremes, such as Gabriel graphs [K. R. Gabriel and R. R. Sokal, Systematic Zoology, 18 (1969), pp. 259-278], relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268], and β-skeletons [D. G. Kirkpatrick and J. D. Radke, Comput. Geom., G. T. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248] with β in [0,2] some interesting questions arise. We show that the spanning ratio for Gabriel graphs (which are β-skeletons with β = 1) is Θ ( √(n)) in the worst case. For all β-skeletons with β in [0,1], we prove that the spanning ratio is at most O(nγ), where γ = (1-log2(1+√(1-β2)))/2. For all β-skeletons with β in [1,2], we prove that there exist point sets whose spanning ratio is at least ( (1)/(2) - o(1) ) √(n) . For relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268] (skeletons with β = 2), we show that there exist point sets where the spanning ratio is Ω(n). For points drawn independently from the uniform distribution on the unit square, we show that the spanning ratio of the (random) Gabriel graph and all β-skeletons with β in [1,2] tends to ∞ in probability as √(log n / log log n).