Home research People General Info Seminars Resources Intranet

Nancy M. Amato, Michael T. Goodrich, Edgar Ramos, "Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization," Discrete and Computational Geometry, 26:245-265, 2001.
Journal(ps, pdf, 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 (1991) celebrated optimal deterministic algorithm. The new algorithm can be viewed as a combination of Chazelle's algorithm and of simple non-optimal randomized algorithms due to Clarkson et al. (1991) and to Seidel (1991). 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.