Beta skeleton

The circle-based 1.1-skeleton (heavy dark edges) and 0.9-skeleton (light dashed blue edges) of a set of 100 random points in a square.

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.

Circle-based definition

The empty regions R_pq defining the circle-based β-skeleton. Left: β < 1. Center: β = 1. Right: β > 1.

Let β be a positive real number, and calculate an angle θ using the formulas

$\theta = \begin{cases} \sin^{-1} \frac{1}{\beta}, & \text{if }\beta \ge 1 \\ \pi - \sin^{-1}{\beta}, & \text{if }\beta\le 1\end{cases}$

For any two points p and q in the plane, let R_pq be the set of points for which angle prq is greater than θ. Then R_pq takes the form of a union of two open disks with diameter βd(p,q) for β ≥ 1 and θ ≤ π/2, and it takes the form of the intersection of two open disks with diameter d(p,q)/β for β ≤ 1 and θ ≥ π/2. When β = 1 the two formulas give the same value θ = π/2, and R_pq takes the form of a single open disk with pq as its diameter.

The β-skeleton of a discrete set S of points in the plane is the undirected graph that connects two points p and q with an edge pq whenever R_pq contains no points of S. That is, the β-skeleton is the empty region graph defined by the regions R_pq.^[1] When S contains a point r for which angle prq is greater than θ, then pq is not an edge of the β-skeleton; the β-skeleton consists of those pairs pq for which no such point r exists.

Lune-based definition

Some authors use an alternative definition in which the empty regions R_pq for β > 1 are not unions of two disks but rather lenses (more often called in this context "lunes"), intersections of two congruent disks with diameter βd(pq), such that line segment pq lies on a radius of both disks and such that the points p and q both lie on the boundary of the intersection. As with the circle-based β-skeleton, the lune-based β-skeleton has an edge pq whenever region R_pq is empty of other input points. For this alternative definition, the relative neighborhood graph is a special case of a β-skeleton with β = 2. The two definitions coincide for β ≤ 1, and for larger values of β the circle-based skeleton is a subgraph of the lune-based skeleton.

One important difference between the circle-based and lune-based β-skeletons is that, for any point set that does not lie on a single line, there always exists a sufficiently large value of β such that the circle-based β-skeleton is the empty graph. In contrast, if a pair of points p and q has the property that, for all other points r, one of the two angles pqr and qpr is obtuse, then the lune-based β-skeleton will contain edge pq no matter how large β is.

History

β-skeletons were first defined by Kirkpatrick & Radke (1985) as a scale-invariant variation of the alpha shapes of Edelsbrunner, Kirkpatrick & Seidel (1983). The name, "β-skeleton", reflects the fact that in some sense the β-skeleton describes the shape of a set of points in the same way that a topological skeleton describes the shape of a two-dimensional region. Several generalizations of the β-skeleton to graphs defined by other empty regions have also been considered.^[1][2]

Properties

If β varies continuously from 0 to ∞, the circle-based β-skeletons form a sequence of graphs extending from the complete graph to the empty graph. The special case β = 1 leads to the Gabriel graph, which is known to contain the Euclidean minimum spanning tree; therefore, the β-skeleton also contains the Gabriel graph and the minimum spanning tree whenever β ≤ 1.

For any constant β, a fractal construction resembling a flattened version of the Koch snowflake can be used to define a sequence of point sets whose β-skeletons are paths of arbitrarily large length within a unit square. Therefore, unlike the closely related Delaunay triangulation, β-skeletons have unbounded stretch factor and are not geometric spanners.^[3]

Algorithms

A naïve algorithm that tests each triple p, q, and r for membership of r in the region R_pq can construct the β-skeleton of any set of n points in time O(n³).

When β ≥ 1, the β-skeleton (with either definition) is a subgraph of the Gabriel graph, which is a subgraph of the Delaunay triangulation. If pq is an edge of the Delaunay triangulation that is not an edge of the β-skeleton, then a point r that forms a large angle prq can be found as one of the at most two points forming a triangle with p and q in the Delaunay triangulation. Therefore, for these values of β, the circle-based β-skeleton for a set of n points can be constructed in time O(n log n) by computing the Delaunay triangulation and using this test to filter its edges.^[2]

For β < 1, a different algorithm of Hurtado, Liotta & Meijer (2003) allows the construction of the β-skeleton in time O(n²). No better worst-case time bound is possible because, for any fixed value of β smaller than one, there exist point sets in general position (small perturbations of a regular polygon) for which the β-skeleton is a complete graph with a quadratic number of edges. In the same quadratic time bound, the entire β-spectrum (the sequence of circle-based β-skeletons formed by varying β) may also be calculated.

Applications

The circle-based β-skeleton may be used in image analysis to reconstruct the shape of a two-dimensional object, given a set of sample points on the boundary of the object (a computational form of the connect the dots puzzle where the sequence in which the dots are to be connected must be deduced by an algorithm rather than being given as part of the puzzle). Although, in general, this requires a choice of the value of the parameter β, it is possible to prove that the choice β = 1.7 will correctly reconstruct the entire boundary of any smooth surface, and not generate any edges that do not belong to the boundary, as long as the samples are generated sufficiently densely relative to the local curvature of the surface.^[4] However in experimental testing a lower value, β = 1.2, was more effective for reconstructing street maps from sets of points marking the center lines of streets in a geographic information system.^[5] For generalizations of the β-skeleton technique to reconstruction of surfaces in three dimensions, see Hiyoshi (2007).

Circle-based β-skeletons have been used to find subgraphs of the minimum weight triangulation of a point set: for sufficiently large values of β, every β-skeleton edge can be guaranteed to belong to the minimum weight triangulation. If the edges found in this way form a connected graph on all of the input points, then the remaining minimum weight triangulation edges may be found in polynomial time by dynamic programming. However, in general the minimum weight triangulation problem is NP-hard, and the subset of its edges found in this way may not be connected.^[6]

β-skeletons have also been applied in machine learning to solve geometric classification problems^[7] and in wireless ad hoc networks as a mechanism for controlling communication complexity by choosing a subset of the pairs of wireless stations that can communicate with each other.^[8]

Notes

1. Cardinal, Collette & Langerman (2009).
2. Veltkamp (1992).
3. Eppstein (2002); Bose et al. (2002); Wang et al. (2003).
4. Amenta, Bern & Eppstein (1998); O'Rourke (2000).
5. Radke & Flodmark (1999).
6. Keil (1994); Cheng & Xu (2001).
7. Zhang & King (2002); Toussaint (2005).
8. Bhardwaj, Misra & Xue (2005).

References

• Amenta, Nina; Bern, Marshall; Eppstein, David (1998), "The crust and the beta-skeleton: combinatorial curve reconstruction", Graphical Models & Image Processing 60/2 (2): 125–135.
• Bhardwaj, Manvendu; Misra, Satyajayant; Xue, Guoliang (2005), "Distributed topology control in wireless ad hoc networks using ß-skeleton", Workshop on High Performance Switching and Routing (HPSR 2005), Hong Kong, China (PDF).
• Bose, Prosenjit; Devroye, Luc; Evans, William; Kirkpatrick, David G. (2002), "On the spanning ratio of Gabriel graphs and β-skeletons", LATIN 2002: Theoretical Informatics, Lecture Notes in Computer Science 2286, Springer-Verlag, pp. 77–97, doi:10.1007/3-540-45995-2_42.
• Cardinal, Jean; Collette, Sébastian; Langerman, Stefan (2009), "Empty region graphs", Computational Geometry Theory & Applications 42 (3): 183–195, doi:10.1016/j.comgeo.2008.09.003.
• Cheng, Siu-Wing; Xu, Yin-Feng (2001), "On β-skeleton as a subgraph of the minimum weight triangulation", Theoretical Computer Science 262 (1–2): 459–471, doi:10.1016/S0304-3975(00)00318-2.
• Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), "On the shape of a set of points in the plane", IEEE Transactions on Information Theory 29 (4): 551–559, doi:10.1109/TIT.1983.1056714.
• Eppstein, David (2002), "Beta-skeletons have unbounded dilation", Computational Geometry Theory & Applications 23 (1): 43–52, arXiv:cs.CG/9907031, doi:10.1016/S0925-7721(01)00055-4.
• Hiyoshi, H. (2007), "Greedy beta-skeleton in three dimensions", Proc. 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), pp. 101–109, doi:10.1109/ISVD.2007.27.
• Hurtado, Ferran; Liotta, Giuseppe; Meijer, Henk (2003), "Optimal and suboptimal robust algorithms for proximity graphs", Computational Geometry Theory & Applications 25 (1–2): 35–49, doi:10.1016/S0925-7721(02)00129-3.
• Keil, J. Mark (1994), "Computing a subgraph of the minimum weight triangulation" (PDF), Computational Geometry Theory & Applications 4 (1): 18–26, doi:10.1016/0925-7721(94)90014-0.
• Kirkpatrick, David G.; Radke, John D. (1985), "A framework for computational morphology", Computational Geometry, Machine Intelligence and Pattern Recognition 2, Amsterdam: North-Holland, pp. 217–248.
• O'Rourke, Joseph (2000), "Computational Geometry Column 38", SIGACT News 31 (1): 28–30, arXiv:cs.CG/0001025, doi:10.1145/346048.346050.
• Radke, John D.; Flodmark, Anders (1999), "The use of spatial decompositions for constructing street centerlines" (PDF), Geographic Information Sciences 5 (1): 15–23.
• Toussaint, Godfried (2005), "Geometric proximity graphs for improving nearest neighbor methods in instance-based learning and data mining", International Journal of Computational Geometry and Applications 15 (2): 101–150, doi:10.1142/S0218195905001622.
• Veltkamp, Remko C. (1992), "The γ-neighborhood graph" (PDF), Computational Geometry Theory & Applications 1 (4): 227–246, doi:10.1016/0925-7721(92)90003-B.
• Wang, Weizhao; Li, Xiang-Yang; Moaveninejad, Kousha; Wang, Yu; Song, Wen-Zhan (2003), "The spanning ratio of β-skeletons", Proc. 15th Canadian Conference on Computational Geometry (CCCG 2003) (PDF), pp. 35–38.
• Zhang, Wan; King, Irwin (2002), "Locating support vectors via β-skeleton technique", Proc. Proceedings of the 9th International Conference on Neural Information Processing (ICONIP'02), Orchid Country Club, Singapore, November 18-22, 2002 (PDF), pp. 1423–1427.