Please use this identifier to cite or link to this item:

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

Authors Cheng, SW
Xu, XF
Issue Date 2001
Source Theoretical Computer Science , v. 262, (1-2), 2001, JUL 6, p. 459-471
Summary 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 triangulation is the sum of the lengths of the edges. In this paper, we show that for beta > l/sin kappa, the beta -skeleton of S is a subgraph of a minimum weight triangulation of S, where kappa- = tan(-1)(3/root2 root3) approximate to pi /3.1. There exists a four-point example such that the beta -skeleton for beta < 1/sin(/3) is not a subgraph of the minimum weight triangulation. (C) 2001 Elsevier Science B.V. All rights reserved.
ISSN 0304-3975
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
beta.pdf 224963 B Adobe PDF