Introduction

A usual strategy in pattern recognition for recognizing a general polygonal object is to decompose it into simpler components, then identify the components and their interrelationships and use this information to determine the shape of the object.

This strategy is one motivation for the development of decomposition techniques, which are to decompose an arbitrary region into convex parts, with the objective being to minimize the number of the latter.

The existing algorithms for convex decomposition can be categorized by two major divisions, corresponding to the exactness of the solution, and the introduction of new points (called Steiner points), respectively.

In the remaining sections, we will concentrate on two algorithms for the decomposition problem that exclude the addition of new points. The first algorithm is an approximate algorithm that works well for monotone polygons. The second algorithm is an exact one that produces an optimal division of an arbitrary polygon, with a trade-off in simplicity and speed.