Abstract
For a planar point set S let T be a triangulation of S and l a line properly intersecting T. We show that there always exists a unique path in T with certain properties with respect to l. This path is then generalized to (non triangulated) point sets restricted to the interior of simple polygons. This so-called triangulation path enables us to treat several triangulation problems on planar point sets in a divide & conquer-like manner. For example, we give the first algorithm for counting triangulations of a planar point set which is observed to run in time sublinear in the number of triangulations. Moreover, the triangulation path proves to be useful for the computation of optimal triangulations.
Original language | English |
---|---|
Pages | 14-23 |
Number of pages | 10 |
DOIs | |
Publication status | Published - 1999 |
Event | Proceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA Duration: 13 Jun 1999 → 16 Jun 1999 |
Conference
Conference | Proceedings of the 1999 15th Annual Symposium on Computational Geometry |
---|---|
City | Miami Beach, FL, USA |
Period | 13/06/99 → 16/06/99 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics