Please use this identifier to cite or link to this item:

Constrained independence system and triangulations of planar point sets

Authors Cheng, Siu-Wing
Xu, Yin-Feng
Issue Date 1994
Summary 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.
Language English
Format Technical report
Files in this item:
File Description Size Format
tr9400.pdf 188.48 kB Adobe PDF