Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

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

BibTeX cite key*:

Kettner2006PseudoTEnum

Title

Title*:

Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

Journal

Journal Title*:

SIAM Journal on Computing

Journal's URL:

http://scitation.aip.org/journals/doc/SIAMDL-home/jrnls/top.jsp?key=SMJCAT

Download URL
for the article:

http://scitation.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJCAT000036000003000721000001&idtype=cvips&prog=normal

Language:

English

Publisher

Publisher's
Name:

SIAM

Publisher's URL:

http://www.siam.org/

Publisher's
Address:

Philadelphia, PA, USA

ISSN:

0097-5397

Vol, No, pp, Date

Volume*:

36

Number:

3

Publishing Date:

October 2006

Pages*:

721-739

Number of
VG Pages:

61

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

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

URL for the Abstract:

http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000036000003000721000001&idtype=cvips&gifs=yes

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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:

@ARTICLE{Kettner2006PseudoTEnum,
AUTHOR = {Br{\"o}nnimann, Herv{\'e} and Kettner, Lutz and Pocchiola, Michel and Snoeyink, Jack},
TITLE = {Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2006},
NUMBER = {3},
VOLUME = {36},
PAGES = {721--739},
ADDRESS = {Philadelphia, PA, USA},
MONTH = {October},
ISBN = {0097-5397},
}


Entry last modified by Anja Becker, 02/28/2008
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/14/2007 09:17:45 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Anja Becker
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
07.02.2008 14:57:25
04/27/2007 09:06:14 AM
05.02.2007 17:34:53
05.02.2007 17:34:32
01/14/2007 09:19:52 PM