A fast las vegas algorithm for triangulating a simple polygon

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

doi:10.1145/73393.73396

A fast las vegas algorithm for triangulating a simple polygon

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present an algorithm that triangulates a simple polygon on n vertices in O(n log^∗ n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

Original language	English (US)
Title of host publication	Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
Publisher	Association for Computing Machinery, Inc
Pages	18-22
Number of pages	5
ISBN (Electronic)	0897912705, 9780897912709
DOIs	https://doi.org/10.1145/73393.73396
State	Published - Jan 6 1988
Event	4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States Duration: Jun 6 1988 → Jun 8 1988

Other

Other	4th Annual Symposium on Computational Geometry, SCG 1988
Country/Territory	United States
City	Urbana-Champaign
Period	6/6/88 → 6/8/88

All Science Journal Classification (ASJC) codes

Geometry and Topology

Access to Document

10.1145/73393.73396

Cite this

@inproceedings{37b6eba5637f4e22a2b01d76ac6a8fba,

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

abstract = "We present an algorithm that triangulates a simple polygon on n vertices in O(n log∗ n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.",

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

year = "1988",

month = jan,

day = "6",

doi = "10.1145/73393.73396",

language = "English (US)",

pages = "18--22",

booktitle = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",

publisher = "Association for Computing Machinery, Inc",

note = "4th Annual Symposium on Computational Geometry, SCG 1988 ; Conference date: 06-06-1988 Through 08-06-1988",

}

Clarkson, KL, Tarjan, RE & Van Wyk, CJ 1988, A fast las vegas algorithm for triangulating a simple polygon. in Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988. Association for Computing Machinery, Inc, pp. 18-22, 4th Annual Symposium on Computational Geometry, SCG 1988, Urbana-Champaign, United States, 6/6/88. https://doi.org/10.1145/73393.73396

TY - GEN

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

AU - Clarkson, Kenneth L.

AU - Tarjan, Robert Endre

AU - Van Wyk, Christopher J.

PY - 1988/1/6

Y1 - 1988/1/6

N2 - We present an algorithm that triangulates a simple polygon on n vertices in O(n log∗ n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

AB - We present an algorithm that triangulates a simple polygon on n vertices in O(n log∗ n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.

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

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

U2 - 10.1145/73393.73396

DO - 10.1145/73393.73396

M3 - Conference contribution

AN - SCOPUS:85032008198

SP - 18

EP - 22

BT - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

PB - Association for Computing Machinery, Inc

T2 - 4th Annual Symposium on Computational Geometry, SCG 1988

Y2 - 6 June 1988 through 8 June 1988

ER -

A fast las vegas algorithm for triangulating a simple polygon

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this