On beta-skeleton as a subgraph of the minimum weight triangulation

Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S. The weight of the trian gulation is the sum of the lengths of the edges. In this paper, we show tha t for beta > l/sin kappa, the beta -skeleton of S is a subgraph of a minimu m weight triangulation of S, where kappa- = tan(-1)(3/root2 root3) approxim ate to pi /3.1. There exists a four-point example such that the beta -skele ton for beta < 1/sin(<pi>/3) is not a subgraph of the minimum weight triang ulation. (C) 2001 Elsevier Science B.V. All rights reserved.