We begin the decomposition
problem with a monotone polygon.
The approximate algorithm sweeps through a monotone polygon in the Y direction
from bottom to top, so at particular Y-value there will be unique left and
right edges of the polygon.

The data structures shown above include (1) a ** stack** storing vertices
which are inward cusps,(2) a

The stack and chains are
maintained as doubly linked lists. The top chain and the stack both contain the
top element. The bottom chain and the stack share the bottom element in a
similar manner.

We process the vertices
from bottom to top, so the data structures enclose the area below the current
Y-value that has been processed.

When the Y sweep encounters
a point, the rules for making connections differs, depending on which chain is
involved.

**Rules for Top Chain****:**

First test the angle at the new point,

if angle < 180, then simply append point to top chain (and continue
sweep), else

make connections between the new point and the elements of the stack, working
backward through the stack, until either:

A. angle at point becomes less than 180 (start a fresh top chain) or

B. angle at stack exceeds 180 (add point to stack) or

C. stack empty (add point to stack).

**Rules for
Bottom Chain****:**

On the bottom chain we wish to ensure that a connection from the new point to
the second element from the bottom of the stack produces a convex region. This
property can be described by saying that the new point can "see" the
stack bottom. In other words, the stack bottom is visible from the new point.

**1.** **Resolve
visibility problems**** **

If a new point cannot see the stack bottom, connections are made from
the previous point on the bottom chain (this point is able to see the stack
bottom) until the new point can see the stack bottom (figure A). We need to
handle extreme cases in which angle at stack exceeds 180. The previous point
can become the bottom of the stack (figure B) or remain on the bottom chain
(figure C).

**2.** **Eliminate inward cusps**

Test the angle at the point,

if angle < 180, then simply append point to bottom chain (and continue
sweep), else

make connections, starting with the bottom of the stack and working upward,
until the angle at the new point is less than 180 (figure A). If the stack is
exhausted, the old stack top and the new point start a new fresh stack, with
the top and bottom chains reversed (figure B).

**Rules for
the Highest Point****:**

Connect the highest point with every point on the stack except the top and
bottom.

Sort points of a monotone
polygon into ascending Y order

**For** each
point in order starting at the bottom **do**

**begin**

**if** this is the first or second point **then** add the point to the stack

**else**** **

**if** point adjacent to bottom chain **then** Resolve
visibility problems

**if** this is the last point **then** apply rules for the highest point

**if** point adjacent to stack top

**if** angle at stack top >180 **then** push point on stack **else** apply rules
for top chain

**else**** if** point
adjacent to top chain **then** apply rules for top chain **else** Eliminate inward cusps on
the bottom chain

**End**

This algorithm is a constant-factor
approximation. It is fast, O(*n*log*n*), and comes within a constant
factor of the best solution.

*A
sample run can be found here.*