<p>So far, the only improvement to <a href="https://doi.org/10.1007/BF02574703" rel="nofollow noreferrer">Chazelle's juggernaut</a> is the 2001 randomized linear-time algorithm by <a href="https://doi.org/10.1007/s00454-001-0027-x" rel="nofollow noreferrer">Amato, Goodrich, and Ramos</a>.  Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.</p>

CC BY-SA 4.0
2010-08-29T11:30:07.530Z
2022-10-16T13:16:21.250Z
2022-10-16T13:16:21.250Z
Jeffε
<p>Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?</p>

<reference-request><cg.comp-geom>
Triangulating a Planar Polygon
Gil Kalai
# Triangulating a Planar Polygon

(Asked by: username_0 on 2010-08-29)

Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?

**Tags:** reference-request, cg.comp-geom

---

## 1 answers

### Answer by username_1 on 2010-08-29. Score: 13 | Accepted answer

So far, the only improvement to [Chazelle's juggernaut](https://doi.org/10.1007/BF02574703) is the 2001 randomized linear-time algorithm by [Amato, Goodrich, and Ramos](https://doi.org/10.1007/s00454-001-0027-x). Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.


---

