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 | |
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