MOLDABLE AND CASTABLE POLYGONS

This paper introduces the concepts of moldability and castability of simple polygons and relates moldability to monotonicity. We detail a THETA(n) algorithm for determining all n forward maximal monotone chains of a simple polygon and apply this algorithm to the problems of determining 2-moldability, 2-castability and the minimum monotone decomposition of a simple polygon (Swaminathan et al., 1992). Our results include a simple optimal algorithm solving the minimum monotone decomposition problem, an optimal algorithm to determine 2-moldability and an O(n log n) algorithm to determine 2-castability.