HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/776
Title: On β-skeleton as a subgraph of the minimum weight triangulation
Authors: Cheng, Siu-Wing
Xu, Yin-Feng
Keywords: Minimum weight triangulation
Beta skeleton
Computational geometry
Issue Date: 2001
Citation: Theoretical Computer Science, v. 262, 2001, p. 459-471
Abstract: 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 β > 1/sin k, the β-skeleton of S is a subgraph of a minimum weight triangulation of S, where k=tan-1(3/√2√3)≈π /3.1. There exists a four point example such that the β-skeleton for β < 1/sin(π /3) is not a subgraph of the minimun weight triangulation.
URI: http://hdl.handle.net/1783.1/776
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
beta.pdf219KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.