15

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?

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
Gil Kalai
  • 6,033
  • 35
  • 73

1 Answers1

13

So far, the only improvement to Chazelle's juggernaut is the 2001 randomized linear-time algorithm by Amato, Goodrich, and Ramos. Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.

Glorfindel
  • 359
  • 1
  • 4
  • 10
Jeffε
  • 23,129
  • 10
  • 96
  • 163