## 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.