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).
When β ≥ 1, the β-skeleton (with either definition) is a subgraph of the Gabriel graph, which is a subgraph of the Delaunay triangulation.