Beta skeleton

When β = 1 the two formulas give the same value θ = π/2, and Rpq takes the form of a single open disk with pq as its diameter.

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.

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

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.

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 dense 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.

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.

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.
The empty regions R pq defining the circle-based β -skeleton. Left: β < 1. Center: β = 1. Right: β > 1.