A lower bound for beta-skeleton belonging to minimum weight triangulations

Given a set S of points in the Euclidean plane, the beta -skeleton (beta > 1) of S is a set of edges with endpoints in S and each edge e in the set sa tisfies the empty-disks condition, i.e., no element in S lies inside the tw o disks of diameter beta /e/ that pass through both endpoints of e. In this paper, we prove a lower bound for beta value (beta = 1/6 root2 root3+45) s uch that if B is less than this value, the beta skeleton of S may not be al ways a subgraph of the minimum weight triangulation (MWT) of S. Thus, we di sprove Keil's conjecture that, for beta = 2/3 root3, the beta -skeleton is a subgraph of the MWT (Keil, 1994). (C) 2001 Elsevier Science B.V. Ail righ ts reserved.