\input CS445Hdr
\begfile{CS445N7.tex of December 4, 1982  7:08 PM}
\def\header{7. Decomposition problems}
\def\ltitle{CS445 - Winter 82}
\def\rtitle{Lectures 13--14}

\chap{\header.}
\sect{7.1. Introduction.}

As we have seen in the previous chapters, It is frequently the case that
a geometrical problem involving an
arbitrary polygon is much harder to answer than its equivalent
for a convex or monotone figure. In many cases, a convenient solution
is to split the given polygon into simpler pieces and solve the problem
separately for each piece.\par

For example,
the point inclusion problem for simple polygons can be reduced in this
way to that of locating a point in a convex, monotone or triangular
subdivision of the plane. Similarly, the intersection of two simple polygons
can be computed by decomposing them into convex pieces,
computing the intersections of those pieces, and putting the results
back together.\par

For the purposes of this chapter, we say that a collection
$F
1,F
2,\ldotss, F
m$ of figures is a {\it decomposition} of a
figure $P$ in $m$ {\it pieces} iff $P=\union
i F
i$, and
any two pieces $F
i$ and $F
j$ have disjoint interiors. The following
is an important fact about polygon decompositions:

\lemma{7.1}{Any simple polygon $P$ can be
decomposed into triangles whose vertices are vertices of $P$.}

The proof of this lemma is given by the algorithms described in
the next sections. It has an important consequence:

\theorem{7.2}{Any simple polygon $P$ of $n$ vertices can be
decomposed into $n-2$ disjoint triangles by adding $n-1$ new edges.}
\proof{The decomposition of $P$ into triangles defines a planar
subdivision, whose edges are either edges or diagonals of $P$.
If we let $m$ be the number of triangles and $d$ the number
of such diagonals, then Euler's theorem gives $(m+1)-(d+n)+n=2$,
i.e. $m=d+1$. On the other hand, by counting the edges of all triangles,
we have $3m=2d+n$, since each triangle has three edges and
each diagonal is counted twice. The two equations together give $m=n-2$.}

\digress{Lemma 7.1 cannot be generalized to three or more dimensions;
for example, the polyhedron $P$ below\fig4
cannot be decomposed into tetrahedra (or any convex polyhedra)
whose vertices are all vertices of $P$.
Even allowing extra vertices, theorem 7.2 fails miserably
in higher dimensions: for example, one can exibit polyhedra with
$n$ vertices that cannot be decomposed into less than $\Omega(n↑2)$
convex pieces.}

Theorem 7.2 is not as important as it might seem, since
in most applications it is not enough to decompose the given polygon
into pieces of a specific kind. Frequently, we also have to decompose
the {\it complement} of the polygon, so that the exterior face of the
resulting subdivision is also of the specified kind; see
for example the point location algorithms of chapter 5. In those cases,
the following result is more relevant:

\theorem{7.3}{Any simple polygon $P$ of $n$ vertices can be transformed
into a triangular subdivision of the plane with 
$2n-2$ regions by adding a vertex at infinity and $2n-3$ new edges.}
\proof{Let $H$ be convex hull of $P$, and $o$ any point inside it.
For every vertex $p$ of $P$ that is on the hull, add to the set of
edges a ray with origin  $p$ and pointing away from $o$; this
decomposes the exterior of $H$ into convex (unbounded) triangles.\par
\hp The interior of $H$ is subdivided by the original edges of $P$
into one or more simple polygons ($P$ itself and its ``pockets'', if
any). By lemma 7.1, each of these can be decomposed into triangles;
the result is a triangular subdivision of the plane with $n+1$
vertices (those of $P$ plus the one at infinity). By theorem
5.8, the total number of edges in this subdivision is $3(n+1)-6=3n-3$
and the number of faces is ${2\over 3}(3n-3)=2n-2$, from which
the theorem follows.}

\digress{A similar result holds if we are interested
in {\it bounded} triangulations: a simple polygon $P$ and its complement
can be decomposed into a bounded triangulation by adding three
finite vertices and $2n+3$ new edges, all but three of them
incident to a vertex of $P$. This result is basic to Kirkpatrick's
algorithm (sect. 5.4.2).}

\sect{7.2. Triangulating a monotone polygon.}

Let's first consider the problem of triangulating a monotone polygon.
A linear-time algorithm for this purpose was given by F. Preparata, M. Garey,
D. Johnson and
R. Tarjan in 1977. The presentation below assumes the polygon $P$
is monotone along the vertical direction, and that
$\langle p
1, p
2, \ldotss, p
n\rangle$ are the vertices of $P$, from
top to bottom\foot1{If we know that $P$ is monotone along a direction $d$
and the vertices of $P$ are given in counterclockwise order,
we produce this sorted list in $O(n)$ time. Furthermore, it is possible
to find in $O(n)$ time a direction along which a given simple polygon $P$
is monotone; an algorithm for this purpose will be presented in section
7.6.}.\par

The algorithm examines the vertices from top to bottom, and outputs
a new piece of the decomposition as soon as it finds three vertices that
define a triangle interior to the polygon. Each triangle is removed from $P$ as soon as it is output; as we shall see later, the portion of $P$ that remains is still a monotone polygon. The part remaining when point $p
i$ is going to be
considered is represented in the algorithm by a stack
$S=\langle s
1, s
2, \ldotss, s
k\rangle$ ($k\geq 2$) of vertices
of $P$, with the following properties:\par

\def\tb{\hangindent 10pt after0 }

\tb\bu\ \ the vertices of the residual polygon $P$ are, from top to bottom,
$\langle s
1, s
2, \ldotss, s
k,$ $p
i,$ $p
{i+1}, \ldotss, p
n\rangle$;

\tb\bu\ \ the points of $S$ are all on the same side (left or right) of
the boundary of $P$ (and also on the same side of $P$);\par

\tb\bu\ \ the angles at $s
2, s
3, \ldotss, s
{k-1}$ are all
concave.\fig6\par

As a consequence of these properties, we have that the next point $p
i$
is adjacent either to $s
1$, to $s
k$, or to both; and the latter case happens
only when $i=n$.\par

\algorithm{7.1}{Triangulation of a monotone polygon.}{
\step 1. [Initialize stack.] {Set $s
1\gets p
1$, $s
2\gets p
2$,
$k\gets 2$, $i\gets 2$.}
\step 2. [Check for termination.] {If $i\geq n$ then stop, else
set $i\gets i+1$.}
\step 3. [Check side.] {If $s
2$ and $p
i$ are on opposite sides of $P$, go to step 4; otherwise go to step 5.}
\step 4. [Remove triangles at top.] {For $j$ from $2$ to $k$, output
the triangle $s
{j-1}s
jp
i$. Set $s
1\gets s
k$, $k\gets 1$ and go
to step 6.}
\step 5. [Remove triangle at side.] {If $k=1$ or the angle
$s
{k-1}s
kp
i$ is concave, go to step 6. Otherwise, output the triangle
$s
{k-1}s
kp
i$, set $k\gets k-1$ and repeat this step.}
\step 6. [Stack $p
i$.] {Set $k\gets k+1$, $s
k\gets p
i$ and
go back to step 2.}}

In order to prove the correctness of this algorithm, we have to show that
the remaining polygon $P$ is always monotone, and that
each triangle that is produced in steps 4 and 5 is entirely inside $P$.
Let's assume the first condition is true at some iteration when we reach 
step 4, and for simplicity let's assume $p
i$ is on the left boundary.\fig4
If the triangle $s
1s
2p
i$ were not entirely interior to $P$, then
it would have to contain some part of an edge of $P$. Since
the edges of $P$ do not cross, this would mean that some vertex is
inside the triangle. But the vertices
$s
3, s
4, \ldotss, s
k$ are all on the right side of the line
$s
1s
2$, because of the conditions on $S$, and the remaining vertices
are all below $p
i$. It follows that the triangle $s
is
2p
i$ is entirely
within $P$, and can be safely output. Since what remains is a monotone
polygon, the same argument carries through for the triangles $p
is
2s
3,
p
is
3s
4, \ldotss, p
is
{k-1}s
k$\par

A similar reasoning shows the correctnes of the triangles
produced in step 5:\fig4
The points $s
1, s
2, \ldotss, s
{k-2}$ are all above $s
{k-1}$, and the
other vertices $p
{i+1}, p
{i+2}, \ldotss$ are all below $p
i$. Therefore,
if the angle at $s
k$ is convex, the triangle $s
{k-1}s
kp
i$ is interior
to $P$ and can be chopped off.
The rest of $P$ will still be a monotone polygon, so the same
argument can be apllied again. It is also easy to check that step 6 does
not destroy the properties of $S$ and $P$.\par

The last vertex $p
n$ is in both sides of the boundary of $P$, and therefore
can be processed either in step 4 or in step 5, indifferently.
Note that a vertex $p
i$ of $P$ is always on the same side of $P$,
except when it becomes $s
1$, so the test in step 3 requires us merely
to remember whether $s
k$ was on the left or on the right side of
the original polygon, and to check that against the side from which $p
i$
comes.\par

\digress{The algorithm above triangulates only the interior of $P$.
To triangulate the exterior, all we have to do is to add a new vertex
at infinity and a ray emanating from each vertex of $P$. The
rays corresponding to the highest and lowest vertices of $P$
can be directed up and down, respectively; the remaining rays
are directed either to the left or to the right, depending on the side
of $P$ to which their origins belong.\par

\dp A {\it bounded} triangulation for the complement of $P$ is a little
harder to get, but it can be obtained by an extension
Graham's convex hull algorithm
(the version that uses linear instead of polar sort). The figures below should
be enough for the reader to deduce the details.\fig5}

\sect{7.3. Decomposition of a simple polygon in monotone pieces.}

We will study next an algorithm for breaking a simple polygon
into pieces that are monotone along a given direction $d$.
Combined with algorithm 7.1, this also allows us to decompose
a simple polygon into triangles.\par

To make things simpler, let's assume the monotonicity axis $d$ is the $y$-axis.
The algorithm below was given by D. Lee and F. Preparata (1977),
as a preliminary step of their point location algorithm,
and runs in $O(n\log n)$ time
(it is not known whether this is the best possible). The algorithm 
is based on the following characterization of monotone polygons,
whose proof is left as an exercise to the reader:\par

\theorem{7.4}{A simple polygon $P$
is monotone along the $y$-axis iff every concave corner
has one neighbor strictly above it and one neighbor strictly below it.\fig4}

Theorem 7.4 says that a polygon is monotone iff it has no
concave angles (let's call
them {\it interior cusps}) pointing up or down.
The algorithm we will describe below detects those cusps, and
makes a cut connecting each upwards-pointing cusp to some vertex
that is above it and is not ``hidden'' by some edge of $P$. 
Downwards pointing cusps are handled in an analogous way.\par

As we remarked before, many applications (like the Lee-Preparata
point-location algorithm, 5.2) require the exterior face
to be monotone, too. According to
theorem 7.4, this means that we have to
eliminate also all {\it exterior cusps} that point up or down\foot1{All
but two (cooresponding to the extremal vertices of $P$),
in case a {\it bounded} monotone subdivision is desired.}.
We can deal with these
cusps in the same way as we dealed with the interior ones, except
that the cuts will decompose the exterior of the polygon.\fig5
This actually simplifies the
algorithm a little bit, since we do not have to check whether the
cusps are internal or external.\par

The algorithm uses the sweeping line principle, and actually performs
two similar passes over the data, in opposite directions. The first pass,
scanning the vertices from top to bottom,
detects and destroys upward-pointing cusps (both interior and exterior);
the second pass takes care of the downward-pointing ones. Two passes
are not strictly necessary, but this introduces considerable simplifications
in the algorithm.\par

During the first pass, the segments intersecting the sweeping line
divide it into one or more intervals, which are represented by the
algorithm as nodes in a balanced search tree $T$, ordered from left to right.
For each interval $I=[\alpha
I, \beta
I]$, delimited left and right by the
edges $\alpha
I$ and $\beta
I$, the algorithm remembers
the lowest vertex $u
I$ of $P$ that is
to the right of $\alpha
I$ and to the left of $\beta
I$.\fig3
The vertex $u
I$ (which
can be the upper endpoint of $\alpha
I$ or $\beta
I$) has the
property that a line connecting it to any point of $I$ will not
cross any other edge of $P$. When the algorithm encounters
an upward-pointing cusp located in some interval $I$, it introduces a cut
connecting the cusp with the vertex $u
I$, thereby destroying the former.\par

Only the first pass of the algorithm is shown below;
the second one is entirely analogous. The first pass assumes the
vertices to be $p
1, p
2, \ldotss, p
n$, from top to bottom\foot1{This
requires an $O(n\log n)$ preliminary sorting step, but this is not the
only bottleneck of the algorithm: maintaining the
tree of intervals $T$ consumes another $O(n\log n)$ time.}.
The algorithm also requires that we remember the two edges incident
to each $p
i$.\par

\algorithm{7.2}{Decomposition of a simple
polygon into monotone pieces (first pass).}{
\step 1. [Initialize.] {Set $T$ to be a tree consisting of a
single interval $I$
with $u
I=(0, +\infty)$, and delimited left and right by two dummy
vertical edges at $x=-\infty$ and $x=+\infty$. Set
$k\gets 1$.}
\step 2. [Check case.] {Examine the edges of $P$ incident to
$p
k$, and classify the latter in one of the following cases:\fig3
go to step 3, 4, or 5, according to the case.}
\step 3. [Change of edge.] {Let $e$ be the edge incident on $p
k$ from
above, and $f$ be the one from below. Locate the consecutive intervals
$I, J$ of $T$ that are separated by the edge $e$.
Set $\beta
I\gets\alpha
J\gets f$, $u
I\gets u
J\gets p
k$ and go
to step 6.}
\step 4. [Upward cusp.] {Let $e$ and $f$, from left to right, be the
edges incident into $p
k$. Locate the interval $I$ in $T$ that
contains $p
k$;
replace it by three consecutive intervals $H=[\alpha
I,e]$, $J=[e, f]$
and $K=[f,\beta
I]$, with $u
H=u
J=u
K=p
k$.
Go to step 6.}
\step 5. [Downward cusp.] {Let $e$ and $f$ be the edges incident to $p
k$,
from left to right. Locate in $T$ the interval $J$ containing $p
k$
(that is now reduced to a single point) and its immediate neighbors $H$
and $K$. Remove these three nodes from $T$ and insert in their place a
new interval $I=[\alpha
H, \beta
K]$ with $u
I=p
k$.}
\step 6. [Get next point.] {If $k=n$, stop: all upward cusps have been
destroyed. Otherwise, set $k\gets k+1$ and go back to step 2.}}

It is easy to see that none of the cuts introduced by this algorithm crosses
an edge of $P$. Each cut is entirely contained in the region delimited
left and right by two edges of $P$, and is such that in this
region there are no
vertices of $P$ whose $y$-coordinate is intermediate between the
endpoints of the cut

:\fig3
From this we conclude that no two cuts intersect, even if each is
generated in a different pass of the algorithm.\par

The algorithm above generates one cut per cusp, but it may happen
that the same cut is produced twice (once in each pass). Since each
cut can destroy at most two cusps (an upward one and
a downward one), the number of cuts generated by algorithm 7.2
is at most twice the minimum required.\par

\vfill\eject\end
(635)\f5