**An Exact Algorithm**

This algorithm produces an
optimal decomposition of polygon into convex regions. It makes double use of dynamic programming techniques:
once in the form of redundancy checking, and once in the form of aggregation.

The algorithm takes n
points (in clockwise order) around the perimeter of an arbitrary polygon. The DECOMPOSE(1,n) procedure would choose one convex region
that includes (1,n) and call itself recursively on the remaining
"fingers" of the original polygon that are not covered by the convex
region(as shown in the figure).

We use an aggregation-style
dynamic program to choose the best convex region. This means if subproblems A
and B are isolated from one another, then an aggregate solution A+B is formed
by combining the best solution for A with the best solution for B. We build up
a convex region from various fragments of its convex perimeter. Although
joining 2 optimal fragments may lead to an inward cusp, the fragments are
nearly isolated. We need to only examine the last arc of the previous fragment
to ensure that a new fragment can be joined.

We call the DECOMPOSE(i,j) procedure to create an ordered list of
vertices between i and j that are visible to both i and j. These vertices are
the candidates for the convex region with segment (i,j). Then we sweep through
the vertex list, using the LOAD procedure to create for
each vertex a table, which records optimal convex fragments starting at i and
ending at the current vertex.(This table is implemented as a stack.) The LOAD procedure look at each previous vertex on the vertex
list, check if it is possible to connect previous to current, call the DECOMPOSE(previous, current), and find the best solution
that results in a concave angle at the previous vertex.

The BEST(pivot,extension)
is called that the stack at pivot is searched to find the best fragment that
can be extended to extension.

We also have a PREPROCESSING procedure which set two properties for
every paire of (i,j): visible(if i is visible
to j) and valid(if i or j is an inward
cusp).

**Pseudocode**

** **

**i****f** edge (i,j)
is done already **then** return old
solution

Initialize the vertex list
with a dummy vertex

**for** k **from** (i+1) **to** j **do**

**if** both edge(i,k) and edge (k,j) are visible **then** add k to the vertex list

**for** each
vertex in the vertex list **do** apply
LOAD(vertex)

optimal <---BEST(j,i) +1

record optimal for edge
(i,j)

**return** optimal

**for** each
previous vertex on the vertex list **do**

**begin **

**if** edge (previous, current) is valid **then**

**begin**

solution<---DECOMPOSE(previous,
current)+BEST(previous, current)

push
the pair (previous, solution) on the current stack

**end **

**end**

**until** stack
(at pivot) is empty **do**

**begin**

old<---stack
(at pivot) top

**if** angle from old to pivot to extension is
greater than 180*

**then** return best-so-far (at pivot)

**else if** old solution < best-so-far **then**

best-so-far
<---old solution

pop
old off stack

**end**

**return** best-so-far

**for** each
edge (i,j) **do**

**if** i is visible to j **then**

**begin**

set
visible true

**if** i or j is an inward cusp **then** set valid true

**end**

This algorithm finds an optimal
solution in time O(n^{4}).