Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



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
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.