Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Brönnimann, Hervé
Kettner, Lutz
Pocchiola, Michel
Snoeyink, Jack

dblp
dblp
dblp
dblp

Not MPG Author(s):

Brönnimann, Hervé
Pocchiola, Michel
Snoeyink, Jack

Editor(s):

Demetrescu, Camil
Tamassia, Roberto
Sedgewick, Robert

dblp
dblp
dblp

Not MPII Editor(s):

Demetrescu, Camil
Tamassia, Roberto
Sedgewick, Robert

BibTeX cite key*:

Kettner2005PseudoTriangEnum

Title, Booktitle

Title*:

Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm

Booktitle*:

Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics
(ALENEX/ANALCO 2005)

Event, URLs

URL of the conference:

http://www.siam.org/meetings/alenex05/

URL for downloading the paper:


Event Address*:

Vancouver, BC, Canada

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

22 January 2005

Event End Date:

22 January 2005

Publisher

Name*:

SIAM

URL:

http://www.siam.org/

Address*:

Philadelphia, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

January

Pages:

98-110

Year*:

2005

VG Wort Pages:

55

ISBN/ISSN:

0-89871-596-2

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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.)

URL for the Abstract:

http://www.mpi-inf.mpg.de/~kettner/pub/pseudot_enum_alenex_05_a.html

HyperLinks / References / URLs:

http://www.mpi-inf.mpg.de/~kettner/proj/PseudoT/



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kettner2005PseudoTriangEnum,
AUTHOR = {Br{\"o}nnimann, Herv{\'e} and Kettner, Lutz and Pocchiola, Michel and Snoeyink, Jack},
EDITOR = {Demetrescu, Camil and Tamassia, Roberto and Sedgewick, Robert},
TITLE = {Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm},
BOOKTITLE = {Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics
(ALENEX/ANALCO 2005)},
PUBLISHER = {SIAM},
YEAR = {2005},
PAGES = {98--110},
ADDRESS = {Vancouver, BC, Canada},
MONTH = {January},
ISBN = {0-89871-596-2},
}


Entry last modified by Christine Kiesel, 06/21/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Lutz Kettner
Created
01/12/2006 10:57:39 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
21.06.2006 11:37:11
21.06.2006 11:36:18
21.06.2006 11:35:14
19.06.2006 09:52:31
19.04.2006 14:10:21
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section