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.
if 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)
for each previous vertex on the vertex list do
if edge (previous, current) is valid then
solution<---DECOMPOSE(previous, current)+BEST(previous, current)
push the pair (previous, solution) on the current stack
until stack (at pivot) is empty do
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
for each edge (i,j) do
if i is visible to j then
set visible true
if i or j is an inward cusp then set valid true
This algorithm finds an optimal solution in time O(n4).