A randomized algorithm for triangulating a simple polygon in linear time Conference Paper uri icon

abstract

  • We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon. Our algorithm is considerably simpler than Chazelle's [3] celebrated optimal deterministic algorithm. The new algorithm can be viewed as a combination of Chazelle's algorithm and of simple nonoptimal randomized algorithms due to Clarkson et al. [6], [7], [9] and to Seidel [20]. As in Chazelle's algorithm, it is indispensable to include a bottom-up preprocessing phase, in addition to the actual top-down construction. An essential new idea is the use of random sampling on subchains of the initial polygonal chain, rather than on individual edges as is normally done.

published proceedings

  • DISCRETE & COMPUTATIONAL GEOMETRY

altmetric score

  • 3

author list (cited authors)

  • Amato, N. M., Goodrich, M. T., & Ramos, E. A.

citation count

  • 17

complete list of authors

  • Amato, NM||Goodrich, MT||Ramos, EA

publication date

  • January 2001