Portal de Periódicos da CAPES

Triangulating a simple polygon in linear time

1991; Springer Science+Business Media; Volume: 6; Issue: 3 Linguagem: Inglês

10.1007/bf02574703

1432-0444

Bernard Chazelle,

Data Visualization and Analytics

We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are the polygon-cutting theorem, which provides us with a balancing scheme, and the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, of our algorithm.