|
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 |
Size | Format |
|---|
| beta.pdf | | 219Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
