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.

Description

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 sets two properties for every pair of (i,j): visible (if i is visible to j) and valid (if i or j is an inward cusp).

Pseudocode

DECOMPOSE(i,j)

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)

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

BEST(pivot, extension)

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

PREPROCESSING

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

Complexity

This algorithm finds an optimal solution in time O(n4).