A fast las vegas algorithm for triangulating a simple polygon

Kenneth L. Clarkson; Robert E. Tarjan; Christopher J. Van Wyk

doi:10.1007/BF02187741

A fast las vegas algorithm for triangulating a simple polygon

Kenneth L. Clarkson, Robert E. Tarjan, Christopher J. Van Wyk

Research output: Contribution to journal › Article › peer-review

35 Scopus citations

Abstract

We present a randomized algorithm that triangulates a simple polygon on n vertices in O(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.

Original language	English (US)
Pages (from-to)	423-432
Number of pages	10
Journal	Discrete & Computational Geometry
Volume	4
Issue number	1
DOIs	https://doi.org/10.1007/BF02187741
State	Published - Dec 1989

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02187741

Cite this

@article{f2a0846dbd5e4153a8cf9e8d4eacb361,

title = "A fast las vegas algorithm for triangulating a simple polygon",

abstract = "We present a randomized algorithm that triangulates a simple polygon on n vertices in O(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.",

author = "Clarkson, {Kenneth L.} and Tarjan, {Robert E.} and {Van Wyk}, {Christopher J.}",

year = "1989",

month = dec,

doi = "10.1007/BF02187741",

language = "English (US)",

volume = "4",

pages = "423--432",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - A fast las vegas algorithm for triangulating a simple polygon

AU - Clarkson, Kenneth L.

AU - Tarjan, Robert E.

AU - Van Wyk, Christopher J.

PY - 1989/12

Y1 - 1989/12

N2 - We present a randomized algorithm that triangulates a simple polygon on n vertices in O(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.

AB - We present a randomized algorithm that triangulates a simple polygon on n vertices in O(n log*n) expected time. The averaging in the analysis of running time is over the possible choices made by the algorithm; the bound holds for any input polygon.

UR - http://www.scopus.com/inward/record.url?scp=0041002459&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041002459&partnerID=8YFLogxK

U2 - 10.1007/BF02187741

DO - 10.1007/BF02187741

M3 - Article

AN - SCOPUS:0041002459

SN - 0179-5376

VL - 4

SP - 423

EP - 432

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

A fast las vegas algorithm for triangulating a simple polygon

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this