TY - GEN

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

AU - Clarkson, Kenneth L.

AU - Tarjan, Robert E.

AU - Van Wyk, Christopher J.

N1 - Publisher Copyright:
© 1988 ACM.

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

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

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 -