Abstract
Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n-2 triangles by adding n-3 nonintersecting diagonals. We propose an O(n log log n)-time algorithm for this problem, improving on the previous best bound of O(n log n) and showing that triangulation is not as hard as sorting Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.
Original language | English (US) |
---|---|
Pages (from-to) | 143-178 |
Number of pages | 36 |
Journal | SIAM Journal on Computing |
Volume | 17 |
Issue number | 1 |
DOIs | |
State | Published - 1988 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Mathematics