On the spanning ratio of gabriel graphs and β-skeletons
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 is not 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 β ∈ [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. 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 β ∈ [1, 2] tends to ∞ in probability as √log n/ log log n.
|Keywords||β-skeletons, Computational geometry, Gabriel graph, Geometric spanners, Probabilistic analysis, Proximity graphs, Spanners|
|Journal||SIAM Journal on Discrete Mathematics|
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