\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 $tH$ and $bH$ with domain $\proj H$ such that $$\eqalign{tH(x)|= \sup H(x)\cr bH(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 bH(x)\leq y\leq tH(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, ya) \in A$ and $(x, yb)\in B$ we have $ya > yb$.\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 bR2$.\tp Let $Xi$ be the $x$-projection of $Fi$, for each $i$; clearly, $Xi$ 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 Xi$.\tp Now let $Xi$ be the leftmost of those intervals. By what we just said, $X{i-1}$ and $X{i+1}$ must both meet $Xi$, 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 $Xi$. 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 $f0, f1, \ldots, fn$ with domain $\proj H$, such that\tp (i) $fi\subset \union \E\P$ for all $i$,\tp (ii) $f{i-1}(x) \leq fi(x)$ for all $x\in\Reals$, and\tp (iii) $fi$ is above $i$ faces and below the remaining $n-i$.} \proof{Let $R1, R2, \ldots, Rn$ be a linear ordering of the faces that is compatible with the vertical ordering. Let $f0$ be the bottom boundary of $H$ and, for $i=1, 2, \ldots, n$, let $$ fi(x) = \alter{$t{ri}(x)$ \hbox{\ if\ } $x\in \proj Ri$,\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 $fi$. It is also obvious that $fi$ is above $Ri$, and , by induction, above all $Rj$ with $1\leq j\leq i$.\pp Now suppose for some $0\leq i