\input TR10WideFormat
\begfile{CurvedMonSep.tex of December 1, 1983 1:06 am --- Stolfi}

% Non-polygonal mnonotone subdivisions and separators
% Incomplete --- abandoned in favor of MonSep.tex, PLoc.tex and descendants.

\def\ltitle{}
\def\rtitle{}
\def\header{Separating chains}

\def\paper#1{\ctrline{\curfont = #1}}
\def\author#1{\ctrline{\rm #1}}
\def\institution#1{\ctrline{\it #1}}

\vskip6mm
\paper{Separating Chains in Monotone Subdivisions of the Plane}
\vskip4mm
\author{Jorge Stolfi and Leo J. Guibas}
\institution{Stanford University and Xerox PARC}
\vskip10mm

\sect{2. Monotone Regions and Chains}

\def\Reals{\hbox{\bf R}}
\def\Plane{\hbox{\bf S}}
\def\proj{\hbox{\rm pr}
x}
\def\Gui{Guibas}
\def\andd{\mathop{\hbox{\ \ and\ \ }}}

Let $\Reals*$ be set $\Reals$ of real numbers augmented with $\set{+\infty,-\infty}$, and let $\Plane*$ be $\Reals\times\Reals*$. For any subset $X\subset \Reals$, we define a {\it chain with domain $X$} (or, in brief, an {\it $X$-chain}) as the graph of a function from $X$ into $\Reals*$.

Let $\proj H$ be the projection of a set $H\subset\Plane*$ on the $x$-axis, and let $H(x)$ be the set of all points of $H$ with abscissa $x$. We define the {\it top} and {\it bottom boundaries} of $H$ as being the chains $t
H$ and $b
H$ with domain $\proj H$ such that
$$\eqalign{t
H(x)|= \sup H(x)\cr
b
H(x)|= \inf H(x)\cr}$$
for all $x\in \proj H$.\fig3

The set $H$ is said to be a {\it monotone figure} iff $H(x)$ is a closed interval, i.e. $$H(x)=\rset{(x,y) \relv y\in\Reals* \andd b
H(x)\leq y\leq t
H(x)}$$ for all $x$ in $X$. Examples of monotone figures are the whole extended plane $\Plane*$, any convex polygon (with its boundary), and a vertical line segment (with its endpoints). Each of the polygons below is also a monotone figure. Note that a monotone figure $H$ need not be connected, and also that its top and bottom need not be disjoint.

\def\E{\Escr}
\def\F{\Fscr}
\def\P{\Pscr}


\sect{2. Regions and vertical ordering.}

We say that a subset $A\subset \Plane*$ is above a subset $B\subset \Plane*$, and $B$ is below $A$, iff $\proj A \inte \proj B \neq \empty$, and for every pair of points $(x, y
a) \in A$ and $(x, y
b)\in B$ we have $y
a > y
b$.\fig3

A {\it (monotone) region} is a connected and nonempty susbset $R$ of $\Reals\times\Reals$ such that $$R(x)=\rset{(x, y)\relv y\in\Reals \andd b
R<y<t
R},$$ for all $x$ in the $x$-projection of $R$. The top and bottom boundaries of a region are therefore disjoint. Examples of monotone regions are the interior of a convex polygon, a vertical line segment, a half-plane. A monotone figure without its top and bottom chains consists of zero or more monotone regions.

It is clear that a a region $A$ is above a region $B$ iff $A$ and $B$ are disjoint and some point of $A$ is above (and on the same vertical as) some point of $B$. Therefore, for any two disjoint regions $A$ and $B$, either $A$ is above $B$, $B$ is above $A$, or their $x$-projections are disjoint. Neither of these two properties hold for subsets of $\Plane*$ that are not connected.

If $A$ is above $B$, and $B$ is above $C$, we cannot in general affirm that $A$ is above $C$, not even if $A$, $B$ and $C$ are pairwise disjoint regions. However, if in addition we have $\proj A\supset \proj B$, or $\proj B\subset \proj C$, it will be the case that $A$ is above $C$. This restricted transitivity is enough to imply the following lemma [\Gui]:

\lemma{1}{For any collection of pairwise disjoint monotone regions, the ``above'' relation is acyclic.}
\proof{Suppose that is not true. Let $F
0, F
1, F
2, \ldots, F
n=F
0$ be a minimum cycle, i.e. a sequence of $n$ distinct regions such that $F
i$ is above $F
{i+1}$ for all $i$, and such that $n$ is minimum. From the definition of ``above'', it folows immediately that $n>2$.\tp

Let $X
i$ be the $x$-projection of $F
i$, for each $i$; clearly, $X
i$ is an interval and meets $X
{i+1}$. If for some $i$ we had $X
{i-1}\supset X
{i}$, then transitivity would hold: $F
{i-1}$ would be above $F
{i+1}$, and the cycle would not be of minimal length ($F
{i}$ could be deleted). For analogous reasons, we cannot have $X
{i-1}\subset X
i$.\tp

Now let $X
i$ be the leftmost of those intervals. By what we just said, $X
{i-1}$ and $X
{i+1}$ must both meet $X
i$, and extend to the right of it. But then $X
{i-1}$ would be above $X
{i+1}$, and we could shorten the cycle by omitting $X
i$. We conclude that no such cycle exists.}

Therefore, the transitive closure of the ``above'' relation is a partial order, called the {\it vertical ordering}, on any set of pairwise disjoint regions.


\sect{3. Monotone subdivisions and separating chains.}

A {\it (monotone) subdivision} of a monotone figure $S$ is a partition $\Pscr$ of $S$ into a finite collection of (disjoint) chains and regions, with the property that the top and bottom of each region in $\Pscr$ is the union of chains of $\Pscr$. Those chains and regions are the {\it edges} and {\it faces} of the subdivision, and are denoted by $\E\P$ and $\F\P$, respectively.\fig3

For example, a decomposition of the plane into a finite number of convex pieces defines a monotone subdivision of $\Reals\times\Reals$ in a rather straightforward way. Similarly, a triangulation of a convex polygon defines a monotone subdivision of its interior.\foot1{Note that the edges of the subdivision may be vertices, sides, or part of sides of the poligonal pieces. Also, vertical sides must be counted as faces rather than edges.}

\theorem{2}{If $\Pscr$ is a monotone subdivision of a figure $H$ with $n$ faces, then there is a collection of $n+1$ chains $f
0, f
1, \ldots, f
n$ with domain $\proj H$, such that\tp
(i) $f
i\subset \union \E\P$ for all $i$,\tp
(ii) $f
{i-1}(x) \leq f
i(x)$ for all $x\in\Reals$, and\tp
(iii) $f
i$ is above $i$ faces and below the remaining $n-i$.}
\proof{Let $R
1, R
2, \ldots, R
n$ be a linear ordering of the faces that is compatible with the vertical ordering. Let $f
0$ be the bottom boundary of $H$ and, for $i=1, 2, \ldots, n$, let
$$ f
i(x) = \alter{$t
{r
i}(x)$ \hbox{\ if\ } $x\in \proj R
i$,\cr
    $f
{i-1}(x)$ \hbox{\ otherwise}\cr}$$
Items (i) and (ii) follow immediately from the definition of subdivision and from the construction of the $f
i$. It is also obvious that $f
i$ is above $R
i$, and , by induction, above all $R
j$ with $1\leq j\leq i$.\pp

Now suppose for some $0\leq i<j\leq n$ we have a point $(x, y)$ of $R
j$ with $y\leq f
i(x)$. Let's assume $i$ is chosen minimum possible, so $(x, f
i(x)) $ is either on $b
H$ or in $t
{R
i}$. Since $(x, y)$ is on a face and $(x, f
i(x))$ is on an edge by (i). Now}

Such a collection of chains is called a {\it complete family of separating chains}. The proof of theorem 2 gives an

\par\vfill\eject\end