Résumé: We present a simple and ef .cient algorithm for decomposing a planar polygon with holes into trapezoids. We show that our trapezoidation algorithm takes O.... n log n.. time, where n is the total number of vertices in the polygon andholes. The previous best algorithm for this problem by Zalik

Langue: Anglais