20061201
On the spanning ratio of gabriel graphs and βskeletons
Publication
Publication
SIAM Journal on Discrete Mathematics , Volume 20  Issue 2 p. 412 427
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 Sspanner if the spanning ratio does not exceed S. For example, for any S there exists a point set whose minimum spanning tree is not an Sspanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42spanner [J. M. Keil and C. A. Gutwin, Discrete Comput. Geom., 7 (1992), pp. 1328]. For proximity graphs between these two extremes, such as Gabriel graphs [K. R. Gabriel and R. R. Sokal, Systematic Zoology, 18 (1969), pp. 259278], relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261268], and βskeletons [D. G. Kirkpatrick and J. D. Radke, Comput. Geom., G. T. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217248] with β ∈ [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 β ∈ [0,1], we prove that the spanning ratio is at most O(nγ), where γ = (1  log2(1 + √1β2))/2. For all βskeletons with β ∈ [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. 261268] (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 β ∈ [1, 2] tends to ∞ in probability as √log n/ log log n.
Additional Metadata  

βskeletons, Computational geometry, Gabriel graph, Geometric spanners, Probabilistic analysis, Proximity graphs, Spanners  
dx.doi.org/10.1137/S0895480197318088  
SIAM Journal on Discrete Mathematics  
Organisation  School of Computer Science 
Bose, P, Devroye, L. (Luc), Evans, W. (William), & Kirkpatrick, D. (David). (2006). On the spanning ratio of gabriel graphs and βskeletons. SIAM Journal on Discrete Mathematics, 20(2), 412–427. doi:10.1137/S0895480197318088
