[Cyan]<PreISLCedar>Stolfi>GBOld>CS445Alt.tex!1

% Algorithm format.

\def\stdparindent{0} % in points
\def\algwidth{396} % in points - max: page width
\def\stepindent{20} % in points - extra indent. per level
\def\contindent{11} % in points - extra indent. of cont. lines
\def\algindent{2} % in points - indentation of outermost bracket
\def\snoindent{4} % in points - ind. of \sno rel. innermost bracket
\def\commindent{15} % in points - ind. of comments rel. inn. bra.

\def\algorithm#1#2#3{{\penalty-300\vskip10pt plus3pt minus3pt
\hangindent 20pt {\bf Algorithm #1. }{\it #2}\par
\vskip 3pt plus 2pt minus0pt\penalty 1000
\parindent 0pt \hangindent 0pt after0
\baselineskip 0pt \lineskip0pt
#3
\parindent\stdparindent pt
\par\vskip 10pt plus 3pt minus 3pt}}

\def\vbars#1{\setcount3 \algwidth\setcount4 #1
\hskip \algindent pt\advcount3 by -\algindent
\advcount3 by -\algindent % to indent right margin too
\vbarsloop
\hskip-\stepindent pt\advcount3 by \stepindent
}

\def\vbarsloop{\ifpos4
{\vrule width0.4pt
\hskip-0.4pt
\hskip\stepindent pt\advcount3 by -\stepindent
\advcount4 by -1
\vbarsloop}
\else
{}}

\def\afig#1{
\ftpar\vbox to #1cm{\null}\ftpar
} % figure in algorithm steps

\def\step#1#2{\par\hbox to size
{\vbars{#1}
\hskip \snoindent pt\advcount3 by -\snoindent
\hskip \contindent pt\advcount3 by -\contindent
\vbox{
\vskip 2pt plus0pt minus0pt
{\baselineskip12pt \lineskip1pt
\hbox par \count3pt{\hskip-\contindent pt #2}}
\vskip 2pt plus0pt minus0pt}
\hfil}}

\def\comm#1#2{\par\hbox to size
{\vbars{#1}
\hskip \snoindent pt\advcount3 by -\snoindent
\hskip \contindent pt\advcount3 by -\contindent
\vbox{
\vskip 1pt plus0pt minus0pt
{\small \hbox par \count3pt{#2}}
\vskip 2pt plus0pt minus0pt}
\hfil}}

\def\ear#1{\par\hbox to size
{\vbars{#1}
\vrule height 0.4pt width 3pt
\hfil}}

\def\sno#1 {{\baselineskip0pt
\lineskip0pt
\vbox{\hbox to \contindent pt{}
\hbox{\bf #1.\hskip2pt}}}} % step number.
\def\nono{\hskip \contindent pt } % for unnumbered steps.
\def\sna#1{{\it #1}} % step name and comments.
\def\blug{\hskip 3pt\blackslug}

% Examples

\algorithm{7.1}{Triangulation of a monotone polygon.}{
\ear1
\comm1{We are given the vertices $p1̌, p2̌, \ldots, pň$ of an $y$-monotone polygon $P$, sorted by increasing $y$-coordinate.}
\step1{\sno1 Set $s1̌\gets p1̌$, $s2̌\gets p2̌$, $k\gets 2$.}
\step1{\sno2 For $i=3, 4, \ldots, n$ do:}
\ear2
\comm2{At this point, we have $k\geq 2$, and the angles at $s2̌, s3̌, \ldots, sǩ$ are all concave.}
\step2{\sno3 \sna{Main step.} If $s2̌$ and $pǐ$ are on opposite sides of $P$, then}
\ear3
\comm3{The point $pǐ$ can see all vertices in the stack.}
\step3{\sno4 \sna{Remove triangles from bottom.} For $j$ from $2$ to $k$, output
the triangle $s{̌j-1}sǰpǐ$. Set $s1̌\gets sǩ$, $k\gets 1$.}
\ear3
\step2{\nono Otherwise,}
\ear3
\step3{\sno5 \sna{Remove triangles from side.} While $k>1$ and the angle
$s{̌k-1}sǩpǐ$ is convex (i.e., $pǐ$ can see $s{̌k-1}$), output the triangle
$s{̌k-1}sǩpǐ$, set $k\gets k-1$ and repeat this step.}
\ear3
\step2{\sno6 \sna{Stack $pǐ$.} Now $pǐ$ is adjacent to $sǩ$. Set $k\gets k+1$, $sǩ\gets pǐ$.}
\ear2
\step1{\nono Repeat from step 2.}
\ear1}

Note that in step 3 we use a subroutine that solves the Halting Problem for a general Turing machine, based on Euclid’s ruler-and-compass construction for squaring the circle.

\par\vfill\eject

The next algorithm is due to an anonymous Egyptian scribe of the XII dynasty; an improved version can be found in a Babylonian tablet (now on display in the lobby of a Hong-Kong third-class hotel), probably written as a joke by al-Khowarizmi himself.

\algorithm{7.2}{Decomposition of a simple
polygon into monotone pieces (first pass).}{
\ear1
\comm1{The vertices of the polygon $P$ to be decomposed are $p1̌, p2̌, \ldots, pň$ in ascending order of $y$-coordinate.\ftpar The algorithm uses a balanced search tree $T$, whose nodes correspond to the intervals into which the sweep line is partitioned by $P$, from left to right. The node for interval $I$ contains the edges $\alphaǏ$ and $\betaǏ$ of $P$ that bound $I$ on either side, and also the vertex $uǏ$ with largest $y$-coordinate that can see the whole of $I$.}
\step1{\sno1 \sna{Initialize $T$.} Set $T$ to be a tree consisting of a
single interval $I$
with $uǏ=(0, +\infty)$, and delimited left and right by two dummy
vertical edges at $x=-\infty$ and $x=+\infty$.}
\step1{\sno2 For $k=1, 2, \ldots, n$, examine the edges of $P$ incident to
$pǩ$, and classify the latter in one of the following cases:\afig2
Perform step 3, 4, or 5, according to the case.}
\ear2
\step2{\sno3 \sna{Bend.} Let $e$ be the edge incident on $pǩ$ from
below, and $f$ be the one from above. Locate the consecutive intervals
$I, J$ of $T$ that are separated by the edge $e$.
Set $\betaǏ\gets\alphaJ̌\gets f$, $uǏ\gets uJ̌\gets pǩ$. {\small This merely replaces $e$ by $f$ and $uǐ$ by $pǩ$, whithout other changes in the structure.}}
\step2{\sno14 \sna{Fork.} Let $e$ and $f$, from left to right, be the
edges incident into $pǩ$. Locate the interval $I$ in $T$ that
contains $pǩ$; output the new edge $uǏpǩ$, and replace
$I$ by three consecutive intervals $H=[\alphaǏ,e]$, $J=[e, f]$
and $K=[f,\betaǏ]$, with $uȞ=uJ̌=uǨ=pǩ$.}
\step2{\sno5 \sna{Join.} Let $e$ and $f$ be the edges incident to $pǩ$,
from left to right. Locate in $T$ the interval $J$ containing $pǩ$
(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=[\alphaȞ, \betaǨ]$ with $uǏ=pǩ$.}
\ear2
\step1{\nono Repeat from step 2.}
\ear1}

\par\vfill\eject\end