MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Amato, Nancy M.
Goodrich, Michael T.
Ramos, Edgar A.		dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
Ramos2000a
Title, Booktitle
Title*:
Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization
Booktitle*:
Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)
Event, URLs
Conference URL::
http://www.cs.ust.hk/tcsc/scg00.html
Downloading URL:
http://www.mpi-sb.mpg.de/~ramos
Event Address*:
Clear Water Bay, Kowloon, Hong Kong
Language:
English
Event Date*
(no longer used):
June 12-14, 2000
Organization:
Association of Computing Machinery (ACM)
Event Start Date:
12 June 2000
Event End Date:
14 June 2000
Publisher
Name*:
ACM Press
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
June
Pages:
201-212
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We describe a randomized algorithm for computing the trapezoidal decomposition
of a simple polygon. Its expected running time is linear in the size of the polygon.
By a well-known and simple linear time reduction, this implies a linear time
algorithm for triangulating a simple polygon. Our algorithm is considerably simpler
than Chazelle's (1991) celebrated optimal deterministic algorithm
and, hence, positively answers his question of whether a simpler randomized
algorithm for the problem exists. The new algorithm can be viewed as a combination
of Chazelle's algorithm and of non-optimal randomized algorithms due to Clarkson
{\it et al.} (1991) and to Seidel (1991), with the essential innovation that sampling
is performed on subchains of the initial polygonal chain, rather than on its edges.
It is also essential, as in Chazelle's algorithm, to include a bottom-up
preprocessing phase previous to the top-down construction phase.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Ramos2000a,
AUTHOR = {Amato, Nancy M. and Goodrich, Michael T. and Ramos, Edgar A.},
 TITLE = {Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization},
 BOOKTITLE = {Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)},
 PUBLISHER = {ACM Press},
 YEAR = {2000},
 ORGANIZATION = {Association of Computing Machinery (ACM)},
 PAGES = {201--212},
 ADDRESS = {Clear Water Bay, Kowloon, Hong Kong},
 MONTH = {June},
}

Entry last modified by Uwe Brahm, 03/02/2010
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)
Edgar A. Ramos		Created
02/23/2001 04:56:42 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker		Edit Dates
02/14/2005 08:28:24 PM
04/10/2001 05:50:57 PM
20.03.2001 17:05:02
20.03.2001 15:53:26
14.03.2001 14:07:55