Folding a simple polygon
Ali A. Kooshesh, Bernard M. E. Moret · 1995
We describe a linear-time algorithm that for& a simple polygon decomposed into elementary convex regions (e.g.. triangles or quadrilaterals) into one of its regions.Using this technique, we develop simple linear-time algorithms, based on the degree sequence of the boundary vertices of the polygon, to color the convex decomposition of the polygon and to construct its dual tree.