|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/46
|
| Title: | Constrained independence system and triangulations of planar point sets |
| Authors: | Cheng, Siu-Wing
Xu, Yin-Feng |
| Issue Date: | 1994 |
| Abstract: | We propose and study a new constrained independence system. We obtain a sequence of results, including a matching theorem for bases of the system and introducing a set of light elements which give a lower bound for the objective function of a minimization problem inthe system. We then demonstrate that the set of triangulations of a planar point set can be modeled as constrained independence systems. The corresponding minimization problem in the system is the well-known minimumweight triangulation problem. Thus, we obtain two matching theorems for triangulations and a set of light edges (or light triangles) that give a lower bound for the minimum weight triangulation. We also prove directly a third matching theorem for triangulations. We show that the set of light edges is a superset of some subsets of edges of a minimum weight triangulation that were studied before. |
| URI: | http://hdl.handle.net/1783.1/46 |
| Appears in Collections: | CSE Technical Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| tr9400.pdf | | 188Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
