Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/776

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(<pi>/3) is not a subgraph of the minimum weight triangulation. (C) 2001 Elsevier Science B.V. All rights reserved.
Subjects
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
Find@HKUST
Files in this item:
File Description Size Format
beta.pdf 224963 B Adobe PDF