Carleton University
Technical Report TR-42
March 1984
Minimum Decompositions of Polygonal Objects
J. Mark Keil & Jörg-Rüdiger Sack
Abstract
Geometrical problems occur frequently in such areas as pattern recognition, image processing, computer graphics and VLSI. Given a geometrical problem an efficient solution is often dependent on the nature of the objects we are dealing with. Objects are often described by polygons. The usual strategy for solving many of these problems on general polygons is to decompose the polygon into simple component parts, solve the problem on each component using a specialized algorithm, and then combine the partial solutions. We survey the existing literature on minimum number and minimum edge-length decompositions. We also give an O(n4 ) algorithm to decompose a rectilinear polygon into the minimum numbers of convex quadrilaterals.