HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item:
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.
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
tr9400.pdf188KbAdobe PDFView/Open

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