| ID:
314585.0,
MPI für Informatik / Algorithms and Complexity Group |
| Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm |
| Authors: | Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack |
| Language: | English |
| Date of Publication (YYYY-MM-DD): | 2006 |
| Title of Journal: | SIAM Journal on Computing |
| Volume: | 36 |
| Start Page: | 721 |
| End Page: | 739 |
| Review Status: | Peer-review |
| Audience: | Experts Only |
| Intended Educational Use: | No |
| Abstract / Description: | This paper studies pseudo-triangulations for a given point set in the plane.
Pseudo-triangulations have many properties of triangulations, and have more
freedom since polygons with more than three vertices are allowed as long as
they have exactly three inner angles less than $\pi$. In particular, there is a
natural flip operation on every internal edge. We present an algorithm to
enumerate the pseudo-triangulations of a given point set, based on the greedy
flip algorithm of Pocchiola and Vegter [Topologically sweeping visibility
complexes via pseudo-triangulations; \emph{Discrete Comput.\ Geom.}\ 16:419
453, 1996]. Our two independent implementations agree, and allow us to
experimentally verify or disprove conjectures on the numbers of
pseudo-triangulations and triangulations of a given point set. (For example, we
establish that the number of triangulations is bounded by than the number of
pseudo-triangulations for all sets of up to 10 points.) |
| Last Change of the Resource (YYYY-MM-DD): | 2007-04-27 |
| External Publication Status: | published |
| Document Type: | Article |
| Communicated by: | Kurt Mehlhorn |
| Affiliations: | MPI für Informatik/Algorithms and Complexity Group
|
| Identifiers: | LOCALID:C1256428004B93B8-512A66D02FF267B9C1257263006F7D0D-...
ISSN:0097-5397 |
| Full Text: |
| Sorry, no privileges |
|
Advanced
