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 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
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
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(n4).