A fast las vegas algorithm for triangulating a simple polygon

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
PublisherAssociation for Computing Machinery, Inc
Pages18-22
Number of pages5
ISBN (Electronic)0897912705, 9780897912709
DOIs
StatePublished - Jan 6 1988
Event4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States
Duration: Jun 6 1988Jun 8 1988

Other

Other4th Annual Symposium on Computational Geometry, SCG 1988
CountryUnited States
CityUrbana-Champaign
Period6/6/886/8/88

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'A fast las vegas algorithm for triangulating a simple polygon'. Together they form a unique fingerprint.

  • Cite this

    Clarkson, K. L., Tarjan, R. E., & Van Wyk, C. J. (1988). A fast las vegas algorithm for triangulating a simple polygon. In Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988 (pp. 18-22). Association for Computing Machinery, Inc. https://doi.org/10.1145/73393.73396