English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm

Brönnimann, H., Kettner, L., Pocchiola, M., & Snoeyink, J. (2005). Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005) (pp. 98-110). Philadelphia, USA: SIAM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-262A-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-262B-D
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Brönnimann, Hervé, Author
Kettner, Lutz1, Author           
Pocchiola, Michel, Author
Snoeyink, Jack, Author
Demetrescu, Camil, Editor
Tamassia, Roberto, Editor
Sedgewick, Robert, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: This paper studies (pointed, or minimal) 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 exactly three have angles less than $\pi$. In particular, there is a natural flip operation on every internal edge. We establish fundamental properties of pointed pseudo-triangulations. We also present an algorithm to enumerate the pseudo-triangulations of a given point set, based on the greedy flip of Pocchiola and Vegter. 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 less than the number of pseudo-triangulations for all sets of less than 10 points; the proof for all $n$ is still to be discovered.)

Details

show
hide
Language(s): eng - English
 Dates: 2006-06-212005
 Publication Status: Issued
 Pages: -
 Publishing info: Philadelphia, USA : SIAM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 279187
Other: Local-ID: C1256428004B93B8-B950E619BAFC14F8C12570F40078A277-Kettner2005PseudoTriangEnum
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Vancouver, BC, Canada
Start-/End Date: 2005-01-22

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, USA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 98 - 110 Identifier: ISBN: 0-89871-596-2