\input TR10GBWideFormat

\begfile{GBb10.tex of October 17, 1983 5:47 pm --- Stolfi}

\chapter{10}{Convex Tracings}

% Additional macros

\def\Thei{1}
\def\Theii{2}
\def\Theiii{3}
\def\Theiv{4}
\def\Thev{5}
\def\Thevi{6}
\def\Thevii{7}
\def\Theviii{8}
\def\Theix{9}
\def\Thex{10}
\def\Thexi{11}
\def\Thexii{12}
\def\Thexiii{13}
\def\Thexiv{14}
\def\Thexv{15}
\def\Thexvi{16}
\def\Thexvii{17}
\def\Thexviii{18}
\def\Thexix{19}
\def\Thexx{20}
\def\Thexxi{21}
\def\Thexxii{22}
\def\Thexxiii{23}

\def\Defi{1}

\def\Eqii{2}
\def\Eqiii{3}

\def\Algi{1}
\def\Algii{2}

\def\PP{{\char P}}
\def\CC{{\char C}}
\def\Col{\mathop{\char C\char o\char l}}
\def\Det{\mathop{\char D\char e\char t}}

\def\The{\bug}

In chapters 3 and 4 of last year's notes we studied convex figures and polygons from the classical point of view. In this and the 
following chapters we will have a second look at convexity and related issues, using the machinery we have just developed for 
dealing with polygonal tracings. As we shall see, the car trip analogy and its related formal concepts (states, tangents, moves, 
turns, and so forth) are quite helpful in the description and verification of the classical algorithms. Above all, we will see that 
the concept of convolution is a very powerful tool for generalizing many classical algorithms and for developing new ones.

\section{10.1. Continuity of tracings}\par


Let's first state a few lemmas that are valid for polygonal tracings in general and will be quite useful in the sequel. These 
properties are easy to justify intuitively by imagining the states of a tour as being traversed by a car that moves in a continuous 
fashion through time. This analogy can be made precise by constructing explicitly for every tour $P$ a continuous function that 
gives the state $P(t)$ of the car at each instant $t$.

\mfig 4cm
Let $P$ be the tour $\langle s
0\,s
0\pr\,s
1\,\ldots\,s
{n-1}\,s
{n-1}\pr\rangle$; then $P(t)$ is a function with period $n$, such 
that $P(i)=s
i$, $P(i+{1\over2})=s
i\pr$ for all integer $i$. Intuitively, it means that from time $i$ to $i+{1\over2}$ the car is 
moving, and from time $i+{1\over2} $ to $i+1$ it is turning. The integer and half-integer values of $t$ are the {\it  critical 
instants} of the tour; the value of $P(t)$ for all other instants can be defined by straightforward interpolation. That is, the 
velocity of the car is constant during a move, and so is its angular velocity during a turn.
\endmfig

\digress{Actually, the exact form of this function is not important, as long as it traverses periodically all states of $P$ in a 
sufficiently ``well-behaved'' way. The above definition makes the ride quite uncomfortable, as the acceleration at the critical 
instants is infinite. By using a slightly more elaborate interpolation scheme, we could have obtained finite acceleration (indeed, 
finite derivatives of all orders) at all instants. However, the simple scheme above will suffice for our needs.}

For this chapter, it is more convenient to consider turns and moves of a tracing as being closed at the beginning and open at the 
end, i.e. as being $[s
i\to s
i\pr)$ and $[s
i\pr\to s
{i+1})$, respectively. Accordingly, we redefine the moving states as 
including the beginning (but not the end) of every move, and similarly for the turning states. The {\it moving} and {\it turning  
instants} are therefore those $t$'s satisfying $i\leq t<i+{1\over 2}$ and $i+{1\over 2}\leq t< i+1$ respectively, for some integer 
$i$. 

With these definitions, we can say that every point that is traversed by a tracing $P$ corresponds to a moving state of $P$, and 
similarly every direction (or tangent) of $P$ corresponds to some turning state of $P$.

\mfig 4cm
Let us define some new terminology. The {\it forward ray} of a state $s$ is the ray with origin $\po s$ and extending towards 
infinity in the direction of $\di s$. We say that a state $s$ {\it faces towards} a point $p$ if $p$ is on the forward ray of $s$ 
but not at $\po s$. We say $s$ {\it faces away from} $p$ if its opposite (the state with same position but opposite orientation) 
faces towards $p$.
\endmfig

A state faces towards (or away from) a line $\lscr$ if it faces towards (or away from) a point of it. Note that a state cannot face 
both towards and away from the same line. We also say that the state $s$ {\it peeks left} (or {\it right}) {\it of} a line $\lscr$ 
if it lies on $\lscr$ and it is oriented towards the left (or right) side of $\lscr$.
\figspace 3cm

For brevity, we will sometimes use a state $s$ in places where its position $\po s$ or its tangent $\ta s$ is intended, as long as 
the the ambiguity can be resolved from the context. For example, if $r$ and $s$ are states, we may write ``$s$ lies to the left of 
$r$'' in lieu of ``the point $\po s$ lies to the left of the line $\ta r$''. Note that if $s$ lies to the left of $r$, it is not 
necessarily the case that $r$ lies to the right of $s$. All four combinations may occur:
\figspace 3cm

Note also that if $s$ lies to the right of $r$, and $r$ to the left of $s$, then either they have parallel tangents, or face 
towards the same point, or face away from the same point.

The most important properties of the function $P(t)$ are that it passes through all states of the tour in the correct order, and 
that {\it both its position and its orientation are continuous, periodic functions of time}. These facts allow us to prove the 
following ``continuity'' properties of any polygonal tour $P$:

\lemma{\Thei}{If $\po P(a)$ and $\po P(b)$ are on opposite sides of a line $\lscr$, then there is a moving instant $t\in (a\sp b)$ 
such that $\po P(t)$ is on $\lscr$.
\figspace 3cm}

\lemma{\Theii}{If $\ta P(a)$ and $\ta P(b)$ pass on opposite sides of a point $p$, then there is some turning instant $t\in(a\sp 
b)$ such that $\ta P(t)$ passes through $p$.
\figspace 3cm}

Lemma {\Thei} follows from the fact that the signed distance between $\po P(t)$ and $\lscr$ is a continuous function of $t$. This 
distance changes sign as $t$ moves from $a$ to $b$, so at some instant it must be zero --- i.e., $\po P(t)$ must be on $\lscr$. The 
proof for the second lemma is quite similar: the signed distance between the tangent line at the car and the point $p$ is easily 
shown to be continuous and periodic. Indeed, in a future chapter we will see that the two lemmata are in a sense the duals of each 
other.

The following are slightly stronger versions of lemmata {\Thei} and {\Theii}. Unlike the weaker versions, the stronger ones cannot 
be generalized to continuous tracings.

\mfig 6cm
\lemma{\Theiii}{Let $P$ be a polygonal tour with no backward moves. If $a<b$, $P(a)$ lies on or to the right of a line $\lscr$, and 
$P(b)$ lies to the left of $\lscr$, then there is a moving instant $c\in [a\sp b)$ such that $P(c)$ peeks to the left of $\lscr$.}

\proof{If the car is not on $\lscr$ at time $a$, then by lemma {\Thei} it must cross that line during $(a\sp b)$. It is easy to see 
that in $[a\sp b)$ there is a last instant $c$ when $\po P(c)$ is on $\lscr$, and that this must happen during (or at the beginning 
of) a non-zero move. Since the car will be to the left of $\lscr$ for the rest of the interval, the car has to be moving (and 
therefore oriented) towards the left of $\lscr$.}
\endmfig

\mfig 5cm
\lemma{\Theiv}{Let $P$ be a polygonal tour with no right turns. If $a<b$, $\ta P(a)$ passes through or to the left of a point $p$, 
and $\ta P(b)$ passes to the right of $p$, then there is an instant $c\in[a\sp b)$ such that $P(c)$ is facing towards $p$.}

\proof{If the line of the car does not pass through $p$ at time $a$, then by lemma {\Theii} it will do so for some instant in 
$(a\sp b)$. It is easy to see that in $[a\sp b)$ there is a last time $c$ when $\ta P(c)$ passes through $p$, and that this must 
happen during (or at the beginning of) a non-zero turn.
\endmfig

\pp Since the tangent will pass to the right of $p$ for the rest of the interval, and it is turning counterclockwise around $\po 
P(c)$, the tangent must be oriented from this point towards $p$, i.e. $P(c)$ is facing towards $p$.}

Lemma {\Theiii} still remains valid if we interchange ``left'' and ``right'' throughout. It still remains valid if when applied to 
a tour $P$ with no {\it forward} moves, except the state $P(c)$ will be peeking the other way.
\figspace 3cm

In a similar way, lemma {\Theiv} remains true if we exchange ``left'' and ``right'' throughout. If $P$ has no {\it left} turns, and 
the tangent sweeps from left to right over $p$, then $P(c)$ will be facing {\it away} from $p$.
\figspace 3cm  

Lemma {\Theiii} has an immediate consequence that is worth pointing out:

\mfig 5cm
\lemma{\Thev}{Let $P$ be a polygonal tour with no backward moves. If $a<b$, $P(a)$ is to the left of a line $\lscr$, and $P(b)$ is 
not, then there is some moving instant $c\in[a\sp b)$ such that $P(c)$ lies to the left of $\lscr$ but is facing towards it.}

\proof{Consider the line $\lscr\pr$ antiparallel to $\lscr$ and passing through $\po P(a)$. Lemma {\Theiii} gives us a moving state 
$P(c)$ with $c\in [a\sp b)$ that peeks to the left of $\lscr\pr$. This state clearly satisfies the theorem.}
\endmfig

The well-known Rolle's Theorem of real analysis states that for any function $f$ continuous and differentiable in an interval 
$[a\sp b]$, there is a point of that interval where the derivative is equal to the average slope $(f(b)-f(a))/(b-a)$. Polygonal 
tracings satisfy a similar property:

\vfil\penalty-200\vfilneg

\lemma{{\Thevi} {\rm (``Rolle's Theorem'')}}{Let $P$ be a polygonal tour that always moves forward and never passes twice through 
the same point. If $a<b$ and $\po P(a)\neq \po P(b)$, then there is a turning instant $c\in (a\sp b)$ such that $\ta P(c)$ is 
parallel to the vector $\po P(b)-\po P(a)$.}

\proof{We will only sketch the proof, since the details are too technical. Let $\lscr$ be the line from $\po P(a)$ to $\po P(b)$. 
Let's first consider some particular cases. If $\po P(t)$ lies always on $\lscr$ for all $t\in(a\sp b)$, then at some instant it 
must be moving in the direction from $P(a)$ to $P(b)$, and the theorem is proved.

\mfig 7cm
\pp Another particular case is when $P(t)$ never enters one of the half-planes of $\lscr$, say the right one. Let then $m$ be a 
point on the car path from $P(a)$ to $P(b)$ that is furthest away from $\lscr$, and let $\lscr\pr$ be the line parallel to $\lscr$ 
and passing through $Pm$. It is not hard to prove that either $\lscr\pr$ or its opposite is a tangent to the tracing at $m$.

\pp But the path from $P(a)$ to $m$ divides the strip between $\lscr$ and $\lscr\pr$ in two pieces; if the tangent at $m$ is 
oriented opposite to $\lscr$, then the path from $m$ to $P(b)$ would have to cross that from $P(a)$ to $m$, contrary to the 
hypothesis. We then conclude the tangent at point $m$ is parallel to $\lscr\pr$, i.e. to the vector from $\po P(a)$ to $\po P(c)$.
\endmfig

\pp In the general case, the path may wander from one side to the other of $\lscr$ finitely many times. If we break this path into 
``jumps'' at the points where it enters and exits $\lscr$, at least one of them will go jump ``forward'' along $\lscr$, from a 
point $\po P(a\pr)$ to a point $\po P(b\pr)$ ahead of it.
\figspace 3cm

\pp We can apply the special case discussed above to this jump, and we conclude that there is some state of it that is parallel to 
the line $\lscr$, proving the theorem.}

\vfil

\ctrpar\textwidth pt{\flower}

\vfil\eject

\section {10.2. Characterization of convex tracings}


Convex tracings have a rather straightforward definition, which we choose to present below in the language of car trips. 

\definition{\Defi}{A polygonal tracing is said to be {\it convex} if it consists of a single tour around a convex polygon, 
traversed in such a way that the polygon lies always to the same side of the car.}

This definition is quite natural, but it is somewhat hard to use in the context of polygonal tracings. The rest of this section 
will be devoted to giving a couple of alternative characterizations of convex tracings, of a more ``local'' character. These 
characterizations are based only in the machinery we have developed in the previous chapter, without explicit reference to the idea 
of convexity.

Convex tracings satisfy many interesting properties. Some of the most  important are listed below: 

\indent $\PP0$. The car never passes twice through the same point or faces twice along the same line.

\hangindent 40pt after0
In more precise terms: for any point $p$ of the plane there is at most one turn $T$ and one {\it moving} instant $t$ such that $\po 
T(t)=p$; for any line $\lscr$, there is at most one turn $T$ and one {\it turning} instant $t$ such that $\ta T(t)=\lscr$. Note 
that there are  infinitely many instants when the car sits still while doing a turn, or faces along the same line while moving, but 
these instants do not count as far as $\PP0$ is concerned.

\indent $\PP1$. The line of the car never passes between two points of the tracing.

\indent $\PP1\pr$. The car never lies between two tangents of the tracing.

\hangindent 40pt after0
Property $\PP1$ says that the line along which the car is facing never passes simultaneously to the left of some point of the 
tracing and to the right of some other point. In a similar vein, $\PP1\pr$ means the car never lies simultaneously to the left of 
some tangent of the tracing and to the right of some other tangent.
\figspace 3cm

\indent $\PP2$. The car moves always forwards or always backwards.

\indent $\PP2\pr$. The car turns always to the left or always to the right.

\indent $\PP3$. The car never faces twice towards the same point.

\indent $\PP3\pr$. The car never peeks twice out of the same line.

\hangindent 40pt after0
Property $\PP3$ means that for any point $x$ of the plane, there is at most one tour $T$ and one {\it turning} instant $t$ such 
that $T(t)$ is facing towards $x$. Note that during any move there are infinitely many instants where the car is facing towards the 
same point, but these do not count as far as $\PP3$ is concerned. In a similar way, $\PP3\pr$  means that for any line $\lscr$ 
there is at most one tour $T$ and one instant $t$ such that $T(t)$ is on $\lscr$ and facing to the right of it.
\figspace 3cm

These properties are not independent of each other; indeed, for any polygonal tracing,
{\def\eqq{\;\;eqv\;\;}
$$ \PP0 \and \PP1\eqq \PP0 \and \PP1\pr\eqq \PP2 \and \PP3\eqq \PP2\pr \and \PP3\pr,\eqno(1)$$}
and each of these pairs implies the tracing is convex (if not empty). We will prove (1) in the following sequence:

\indent $\hbox{\it Convexity} \implies \PP0 \and \PP1\and \PP1\pr$ (theorem {\Thevii});

\indent $\PP0 \and \PP1\implies \PP2 \and \PP2\pr \and \PP3\and \PP3\pr$ (theorem {\Theviii});

\indent $\PP2 \and \PP3\implies \PP0 \and \PP1$ (theorem {\Theix});

\indent $\PP0 \and \PP1\implies\hbox {\it convexity}$ (theorem {\Thex});

\indent $\PP2\pr \and \PP3\pr\implies \PP0 \and \PP1\pr$ (theorem {\Thexi});

\indent $\PP0 \and \PP1\pr\implies\hbox {\it convexity}$ (theorem {\Thexii}).

It is not hard to prove that $\PP3$ remains true in the limiting case when the point goes to infinity. That is, {\it in a convex 
tracing the car faces in each direction at most once}. Indeed, we could have replaced $\PP3$ by this weaker property, and it would 
still be the case that $\PP2$ and $\PP3$ implies convexity.

\theorem{\Thevii}{A convex tracing satisfies $\PP0$, $\PP1$ and $\PP1\pr$.}

\proof{Immediate.}

\theorem{\Theviii}{If a polygonal tracing satisfies $\PP0$ and $\PP1$, then it contains at most one tour, and satisfies also 
$\PP2$, $\PP2\pr$, $\PP3$, and $\PP3\pr$.}

\proof{First, note that $\PP0$ forbids null moves and turns, for during them the car stays for infinitely many instants on the same 
point and facing into the same tangent, respectively.

\mfig 4cm
\pp Suppose now a tour of the tracing contained both forward and backward moves; then there would be a forward move $[s
i\to 
s
i\pr)$ followed by a backward one $[s
{i+1}\to s
{i+1}\pr)$. But then, for any state $r$ in the intervening turn $(s
i\pr\to 
s
{i+1})$, the tangent $\ta r$ would pass between the points $\po s
i$ and $\po s
{i+1}\pr$ of the tracing, contradicting $\PP1$.
\endmfig

\pp Suppose now a tour contained both left and right turns; there would be a left turn $[s
{i-1}\pr\to s
i)$ followed by a right 
one $[s
i\pr\to s
{i+1})$. Since the moves are all done in the same way, the points $\po s
{i-1}$ and $\po s
{i+1}\pr$ would lie on 
opposite sides of the tangent of the move $[s
i\to s
i\pr)$, again contradicting $\PP1$.

\pp Therefore, all moves and turns on the same tour are performed in the same way. Now suppose the tracing contains two distinct 
tours $R$ and $S$. Each contains at least three non-colinear points, and therefore we can always find a line $\lscr$ that passes 
between two points of $R$ and also between two points of $S$. By lemma {\Theiii}, there are two moving states $r
1$ and $s
1$ that 
peek to the right of $\lscr$, and two others $r
2$ and $s
2$ that peek to the left of it, all with distinct positions by $\PP0$.
\figspace 3cm

\pp It is easy to check that, no matter how they are arranged along $\lscr$, one of the four tangents will pass between two of the 
four points, contradicting $\PP1$. We conclude therefore that the tracing has at most one tour $T$, and satisfies $\PP2$ and 
$\PP2\pr$.

\pp Let's now suppose there are two distinct turning instants $a$ and $b$ such that $T(a)$ and $T(b)$ both face towards some point 
$x$. These two states cannot have the same tangent, because of $\PP0$; therefore, there is some line $\lscr$ that passes through 
$x$ all of whose points (except $x$) lie between the two tangents at $a$ and $b$.
\figspace 3cm

\pp The points $T(a)$ and $T(b)$ must be on opposite sides of $\lscr$, and by lemma {\Thei} the car must pass twice through 
$\lscr$, once when going from $T(a)$ to $T(b)$ and a second time when returning from $T(b)$ to $T(a)$. Because of $\PP1\pr$, it 
cannot cross the line anywhere except on $x$; but then it will pass twice through the same point, contradicting $\PP0$.

\pp To conclude, let us suppose there are two moving instants $a$ and $b$ when $T$ is peeking out of some line $\lscr$. The two 
states $T(a)$ and $T(b)$ have different positions because of $\PP0$; let $x$ be any point on $\lscr$ between them. By lemma 
{\Theii}, there are two distinct turning instants (one when going from $T(a)$ to $T(b)$ and the other when returning from $T(b)$ to 
$T(a)$) when the line of the car passes through the point $x$. The tangents at those instants must coincide with $\lscr$ or its 
opposite, otherwise they will pass between $\po T(a)$ and $\po T(b)$.
\figspace 3cm

\pp Because of $\PP0$, those two tangents must be opposite to each other. But then the moves to which $T(a)$ and $T(b)$ belong lie 
on the same side of $\lscr$, and therefore in opposite sides of the two tangents, contradicting $\PP1\pr$.} 

Therefore, $\PP0$ through P$3\pr$ are valid for convex tracings. What is more important, these properties characterize convextity, 
as the next two theorems show: 

\theorem{\Theix}{If a tracing satisfies $\PP2$ and $\PP3$, then it satisfies also $\PP0$ and $\PP1$.}

\mfig 3cm
\proof{First, notice that, because of $\PP3$, in each tour of the tracing all turns are made in the same way: null turns are 
automatically forbidden, and two consecutive turns in opposite directions always contain two states that face towards the same 
point.
\endmfig

\mfig 6cm
\pp Now suppose there were two distinct tours $R$ and $S$. As in the proof of theorem {\Theviii}, there should be some line $\lscr$ 
that passes between two points of $R$ and also between two points of $S$. By lemma {\Theiii}, there should be two states $r
1$ of 
$R$ and $s
1$ of $S$ peeking to the left of $\lscr$, and two others $r
2$ and $s
2$ peeking to the right of it. Then a point $x$ on 
$\lscr$ sufficiently far away in the direction of $\di \lscr$ would be to the right of $r
1$ and $s
1$ and to the left of $r
2$ and 
$s
2$. By lemma {\Theiv}, for two turning instants $c$ and $c\pr$ we would have $R(c)$ and $S(c\pr)$ facing towards $x$, 
contradicting $\PP3$. So, there is at most one tour.
\endmfig

\pp Let us now prove that $\PP1$ holds. Assume first all turns are to the left, and suppose there is some turning state $P(s)$ 
whose tangent passes between two points of the tour. Then by lemma {\Theiii} there would be a moving state $P(c)$ peeking to the 
left of $\ta P(s)$. If $c\pr$ is the end of the corresponding move, then $P(c\pr)$ lies to the left of $P(s)$; there would be an 
instant $d\in[c\pr\sp s)$ when $P(d)$ is to the left of $\ta P(s)$ but facing towards it.
\figspace 3cm

\pp Then if we were to choose $x$ on the forward ray of $P(s)$ and sufficiently far away, $x$ would lie to the right of $P(c)$ and 
to the left of $P(d)$; by lemma {\Theiv}, there would be a turning instant $e\in(c\sp d)$ when $P(e)$ faces towards $x$. But $P(s)$ 
also faces towards $x$, a contradiciton. A similar argument holds if all turns are to the right, so we conclude $\PP1$ holds.

\mfig 4cm
\pp Finally, let's show $\PP0$ holds. Clearly, $\PP3$ forbids two turning instants with same tangent. Suppose there were two moves 
$[s
i\to s
i\pr)$ and $[s
j\to s
j\pr)$ passing through the same point $x$. If the tour is moving backwards, then $s
i\pr$ and 
$s
j\pr$ are distinct turning states that face towards point $x$. If the tour moves forward, then the turns ending at $s
i$ and 
$s
j$ contain two states that face towards some point in a neighborhood of $x$ (a special argument is needed for the case when the 
two moves have opposite orientations, but we will leave the details to the reader). Either case, $\PP3$ is contradicted.}
\endmfig

\theorem{\Thex}{A nonempty tracing that satisfies $\PP0$ and $\PP1$ is convex.}

\proof{By theorem {\Theviii}, the tracing contains a single tour $\langle s
0\, s
0\pr\, s
1\, s
1\pr\, \ldots\, s
{n-1}\, 
s
{n-1}\pr\rangle$. The path traversed by the car is the polygon $\s P=\langle \po s
0, \po s
1, \ldots, \po s
{n-1}\rangle$, which 
is simple because of $\PP0$. If the car always turns counterclockwise, then each move $[s
i\to s
i\pr)$, and therefore all points 
of the tracing, will lie to the left of the tangent supporting the next move $[s
{i+1}\to s
{i+1}\pr)$. So, the polygon $\s P$ is 
contained in the intersection of the left half-planes of the lines that support its edges; this means it is a convex polygon.

\pp A similar argument holds for the case when all turns are to the right.}

\theorem{\Thexi}{If a tracing satisfies $\PP2\pr$ and $\PP3\pr$, then it also satisfies $\PP0$ and $\PP1\pr$.}

\theorem{\Thexii}{A nonempty tracing that satisfies properties $\PP0$ and $\PP1\pr$ is convex.}

The proofs of these theorems will become trivial after we have studied the concept of geometric duality, so we will not bother to 
give them here. Of course, both theorems can also be proved directly, by ``dualizing'' the proofs of theorems {\Theix} and {\Thex}.

In conclusion, $\PP0$ and $\PP1$ completely characterize convex tracings, and the same is true of $\PP2$ and $\PP3$, $\PP0$ and 
$\PP1\pr$, and $\PP2\pr$ and $\PP3\pr$. Note that they are almost ``local'' properties and can be expressed using only the language 
of polygonal tracings, as we wanted.

\section {10.3. Product and convolution of convex polygons}


Property $\PP1\pr$ means all tangents of a convex tracing are oriented in the same way, either all clockwise or all 
counterclockwise, as seen from any point $p$ on the polygon; property $\PP1$ says this orientation will be the same for all $p$'s. 
We will speak of this common orientation as {\it the orientation of the tracing}. Independently of its orientation, the car may 
move counter- or clockwise, and that coincides with the way the car turns at the corners. Threfore, convex tracings come in four 
different flavors:
\figspace 4cm
The first of the above will be sometimes referred to as the {\it standard kind} of convex polygon.

The interior of a convex tracing $P$, i.e. the set of points of the plane with nonzero winding numbers, coincides with the interior 
of the convex polygon (in the classical sense) defined by the vertices of of $P$. The winding number $w(p, P)$ of a point $p$ 
inside the polygon will be either $+1$ or $-1$, depending on whether the car moves counter- or clockwise. Therefore, for two convex 
tracings $P$ and $Q$, the number $w(p, P\cdot Q)$ will be nonzero only in the intersection of the two convex polygons corresponding 
to $P$ and $Q$, which is itself a convex polygon. This suggests that the product of two convex tracings should be a convex tracing; 
and, indeed,  the following is true:

\theorem{\Thexiii}{The product of two convex tracings that intersect propertly and have the same orientation is either empty or 
convex.}\par

\proof{If every point of the plane has zero winding number with respect to one of the polygons (or both), the product will be 
empty. Otherwise, let $p$ be such a point interior to both; as seen from it, all tangents to $P$ and $Q$ are oriented the same way.

\pp By checking the four possible cases, it is easy to see that, independently of the ways $P$ and $Q$ move, all pieces of them 
that survive in the product tracing will be traversed the same way, either all forwards or all backwards. A moving state will be in 
the product if and only if it is on an edge of one polygon and interior to the other, i.e. on an edge of the intersection of the 
two polygons. It is easily seen that the vertices of the product are precisely the vertices of the intersection, which is a convex 
polygon. Since all edges of the product are oriented and traversed the same way, we can conclude the turns also will be made the 
same way.}

Convex tracings are closed also under convolution. In order to show this result, however, we need another characterization of 
convex polygons, based on the following property:

\indent $\PP4$. The car faces exactly once along any direction.

Property $\PP4$, like $\PP3$, refers only to the turning instants of the tracing. As we remarked before, this property can replace 
$\PP3$ in the characterization of convex polygons:

\theorem{\Thexiv}{A tracing is convex if and only if it is nonempty and satisfies $\PP2$ and $\PP4$.}

\proof{Let's first prove that $\PP2$ and $\PP3$ imply $\PP4$. A tracing satisfying $\PP2$ and $\PP3$ is convex, so it consists of a 
single tour $P$ that turns and moves always the same way. Since it returns to the initial orientation after each period, it must 
face along each direction of $S^1$ at least once. 

\mfig 4cm
\pp Now suppose there are two distinct turning instants $a$ and $b$ such that $P(a)$ and $P(b)$ have the same direction. They 
cannot have the same tangent, because of $\PP0$. Without loss of generality, let's assume $P(b)$ is to the left of $P(a)$ if $P$ is 
turning left, and to the right of $P(a)$ otherwise. Then, since turns are open at the end, there is some instant $a\pr$ during the 
turn of $a$ for which the state $P(a\pr)$ faces towards a point on the forward ray of $P(b)$, contradicting $\PP3$.
\endmfig

\pp Let's then assume $\PP2$ and $\PP4$ hold, and let's prove the tracing is convex. First, note that in each turn of the tracing 
the moves must be all forward or all backward: null turns are immediately excluded by $\PP4$, and any pair of adjacent turns with 
opposite directions would contain a pair of parallel turning states. But any tour that turns always the same way faces at least 
once along any direction of $S^1$, so the tracing consists of exactly one tour.

\mfig 5cm
\pp Now suppose there were some tangent passing between two points of the tracing; then on some side of the tangent there will be 
an instant when the car is facing parallel to the tangent, contradicting $\PP4$. Therefore, we have property $\PP1$: the tangent of 
the tour never passes between to points of the tracing.

\pp Finally, let us show the tracing satisfies $\PP0$. The car never faces twice along the same line (because of $\PP4$). It also 
never passes twice through the same point. If it did so, consider the two tangents at that point: if they are identical they 
contradict $\PP4$, if they are opposite then $P$ lies all on one line, and if they are distinct then $\PP1$ is violated.
\endmfig

\pp Since $\PP0$ and $\PP1$ hold, we conclude the tracing is convex.}

Now we are ready to prove the following result:

\theorem{\Thexv}{The convolution of two transverse convex tracings $P$ and $Q$ with same orientation is a convex tracing.}

\proof{Each turning state of the convolution corresponds to the sum of two parallel turning states of $P$ and $Q$. Since $P$ and 
$Q$ face in any direction exactly once, each turning state of one tracing can be paired with exactly one vertex of the other; it 
follows $P\ast Q$ also points in each direction exactly once.

\pp Each move of the convolution is the sum of a move of $P$ with a matching turn of $Q$, or vice-versa. By hypothesis, $P$ and $Q$ 
are oriented the same way. If they also move the same way (both forwards or both backwards) then they both turn the same way (left 
or right). In this case, either all moves of the convolution are ordered as in $P$ and $Q$, or all are time-reversed.

\pp On the other hand, if $P$ and $Q$ move in opposite ways (one forwards and one backwards) then one turns left and the other 
turns right; so, only one of them will have its moves time-reversed in the convolution. In any case, the moves of the convolution 
will be either all forward or all backward.

\pp Therefore, the convolution $P\ast Q$ satisfies properties $\PP2$ and $\PP4$, and is convex by theorem {\Thexiv}.}

In fact it is not difficult to see that the sequence of moves of the convolution is obtained by ``merging'' the moves of $P$ and 
$Q$ cyclically according to their slopes. That is, the convolution operation inserts between two consecutive moves $m
1$ and $m
2$ 
of $P$ all those moves of $Q$ whose orientation lies in the arc $(\di m
1\sp \di m
2)$. This fact is extremely important, for it 
shows how to compute in $O(n+m)$ time the convolution of two convex polygons of $n$ and $m$ edges.

If $P$ and $Q$ are two transverse convex polygons oriented in {\it opposite} ways (one clockwise and the other counterclockwise), 
then $P\ast Q$ is in general not convex, not even simple. The figure below shows an example:
\figspace 3cm

The results of such convolutions may not be as nice as convex polygons, but they still satisfy property $\PP4$: each direction 
occurs exactly once. Tracing with this property are called {\it monostrophic}, and they form an interesting class by themselves. It 
is easy to prove that a monostrophic tracing consists of a single tour whose turns are either all to the left or all to the right.

They therefore satisfy $\PP2\pr$, but none of the remaining properties (except for ``half'' of $\PP0$: the car does not face twice 
along the same line). A monostrophic tracing may contain forward, backward and null moves, and may cross itself many times. The 
convolution of two monostrophic tracings is monostrophic, and it too consists of merging the moves of the two operands in cyclic 
order of slope. As we will see later on, this property alone makes monostrophic tracings interesting. We will see also that they 
are in some ways related to star-shaped polygons.

It is worth noting that the fundamental theorem has an especially simple interpretation  when the tracings $P$ and $Q$ are convex:

\theorem{\Thexvi}{Two convex tracings $P$ and $Q$ with same orientation have a non-empty intersection if and only if the origin $O$ 
is contained inside the convolution $P\ast Q^{-I}$.}

\proof{By the fundamental theorem, we have $w(O, P\ast Q^{-I})\neq0$ if and only if $\delta(P\cdot (Q^{-I})^{-I})\neq 0$. The 
second expression simplifies to $\delta(P\cdot Q)\neq 0$, which is the same as saying that the intersction of $P$ and $Q$ have a 
nonempty intersection.}

\section{10.4. Point inclusion and line intersection}


In the simplest variant of the {\it point inclusion problem}, we are given a point $x$ and a convex polygon $P$, and we want to 
know whether $x$ is inside $P$ or not. If we think of polygons as tracings, then this problem consists essentially in computing the 
winding number $w(x, P)$ of a point $x$ with respect to a convex tracing $P$.

The definition of winding number in section 9.6.4 practically gives an algorithm for computing $w(x, P)$ for general tracings: we 
seclect an arbitrary ray out of $x$, and count how many moves of $P$ cross that ray from right to left. The main trouble with this 
method comes from degeneracies: moves that begin or end on the ray, or that lie entirely on it.

We know that there are many rays that avoid all such degeneracies, but finding one of them is by itself a nontrivial problem. Since 
the set of ``bad'' rays has measure zero, we might pick one at random and trust our luck, and perhaps try again if we discover it 
is bad. A better way is to take care of degeneracies explicitly. As we discussed in section 9.6.4, we can count as $\pm{1\over2}$ 
the moves that just touch the ray, and ignore those that lie in it\foot\dag{An alternative method, perhaps simpler in practice, was 
suggested in section 5.4}. With this technique, we can choose the ray that makes the testing of each move more convenient, for 
example the one parallel to the $x$-axis. The straightforward implementation of this idea runs in time $O(n)$ for a tracing of size 
$n$, assuming we can enumerate the moves that fast

The last remark brings up the issue of how the tracing is represented in the computer. This can be seen as related to the tradeoff 
between query cost vs. preprocessing cost that we have seen several times before, beginning with chapter 5: if we have to check 
``on line'' a large number of points for inclusion in the same polygon, we may consider preprocessing it into a representation that 
makes for more efficient queries. On the other hand, the tracing may be given in such a form that the simple enumeration of its 
moves takes more than linear time.

A polygonal tour $S=\langle s
0\,s
0\pr\,s
1\,s
1\pr\,\ldots\,s
{n-1}\,s
{n-1}\pr\rangle$ whose moves are all forward can be 
represented by an array $\prg{s}$ with indices $0$ through $n-1$ containing the vertices $\prg{s[$i$]}=\po s
i=\po s
i\pr$, in the 
order in which they are traversed. The orientation of the critical states can be reconstructed from this information: the 
orientation of $s
i$ is parallel to the vector from $\prg{s[$i-1$ mod $n$]}$ to $\prg{s[$i$ mod n]}$, and that of $s
i\pr$ is from 
$\prg{s[$i$ mod n]}$ to $\prg{s[$i+1$ mod $n$]}$\foot\ddag{We assume the operation $\prg{$i$ mod $n$}$ is defined according to the 
mathematical convention, i.e. $\prg{$i$ mod $n$}\in[0\sp n)$. For example, $\prg{$(-11)$ mod $5$}=4$. Note that many programming 
languages have a counterfeit version of $\prg {mod}$ that gives $\prg{$(-11)$ mod $5$}=-1$.}. Once we know the orientations of all 
critical states, we know also the turns of the tour. Analogous considerations hold for the case when all moves are backward. If the 
tour contains both forward and backward moves, we need an extra bit array $\prg{forward[$i$]}$, to specify how each move $[s
i\to 
s
i\pr)$ is done.

\digress{Alternatively, we might think of having $n$ bits that tell whether each turn is clockwise or counterclockwise. This is not 
as good as having one bit per move, since it is not enough for determining the orientations of the states: we cannot tell whether a 
move is forward or backward, but only whether two edges are traversed in the same or in opposite ways.

\dp If the tour contains zero moves, then one extra bit per node is no longer enough: we have to give explicitly the orientation of 
those null moves. One of the many ways of doing this is to have two arrays of $n$ bits, $\prg{null}$ and $\prg{forward}$. If 
$\prg{null[$i$]}$ is true, then the move $[s
i\to s
i\pr)$ is null: we then have $\po s
i=\po s
i\pr=\po s
{i+1}$, so$\prg{s[$i+1$ 
mod $n$]}$ is superfluous, and can be used to store the direction $\di s
i=\di s
i\pr$ of the move. If $\prg{null[$i$]}$ is false, 
then the move is nonzero, and $\prg{forward[$i$]}$ specifies the way the car moves during it. This schema is economical in space 
but somewhat hard to manipulate (consider for example what happens when there are two or more null moves in sucession, or all moves 
are null). If space is not a problem, it is preferrable to store both positions and directions of all states, as four coordinates 
per point.}

In more realistic situations, when we have to represent many tours simultaneously, a linked representation is almost mandatory. In 
that case, it is convenient to replace the array $\prg{s}$ (and the bit vectors $\prg{null}$ and $\prg{forward}$, when present) by 
a singly- or doubly-linked circular list, with one node per vertex. More elaborate structures may be necessary to support the class 
of operations required by the application; for example, in an interactive graphics program we may have to locate quickly the vertex 
that is closest to the graphcs cursor. This may require the polygon to be represented by a tree or some other hyerarchical 
structure. It is impossible to give a standard data structure covering all cases, so when describing an algorithm we will use the 
simplest representation that is compatible with it. In most cases, this representation will be just a linear array of vertex 
coordinates, as discussed above. 

\subsection {10.4.1. Point inclusion by polar search}

\mfig 7cm
We can get a faster point inclusion test by exploiting the fact that a convex polygon is {\it star shaped} with respect to any 
interior point $c$; i.e., any ray out of $c$ meets the boundary of the polygon in exactly one point. Then, according to $\
PP0$, there is exactly one moving instant when the car is on that ray.

Now consider the ray $r$ from $c$ that passes through the given point $p\neq c$, and consider the portion $r\pr$ of $r$ starting at 
$p$. The ray $r\pr$ may intercept only a single move of $P$, namely the one intercepted by $r$. So, to compute the winding number 
of $p$ we only have to find that move and test whether it passes between $p$ and $c$ or not. The move that intercepts $r$ can be 
found by a sequential search, where we look for the only $i$ such that the oriented line $cp$ is in the range $[cv
i\sp cv
{i+1})$.
\endmfig

Note that the angles between consecutive vertices, as seen from $c$, are either all clockwise or all counterclockwise, depending on 
whether the polygon is moving right or left, respectively. In the second (standard) case, the index $i$ we are looking for is the 
first one (in ciclic order) for which the angle between $cp$ and $cv
{i+1}$ is positive. If the polygon moves clockwise, then we 
should look for the first $i$ that gives a negative angle.

The basic tool we will use for this search is the predicate $\CCW(p, q, r)$, that is defined to be true if and only if the three 
points $p, q$, and $r$ are the vertices of a proper triangle in counterclockwise order, i.e. if the three points are distinct and 
the line from $p$ to $r$ is to the left of the line from $p$ to $q$. Two similar predicates are: $\CW(p, q, r)$, which is true if 
$pqr$ is a proper triangle in clockwise order; and $\Col(p, q, r)$, which is true if there is som straight line that passes through 
$p, q$, and $r$. These predicates satisfies the following relationships:

\indent $\CC1$. $\CCW(p, q, r)eqv\CCW(q, r, p)eqv\CCW(r, p, q)$.

\indent $\CC1\pr$. $\CW(p, q, r)eqv\CW(q, r, p)eqv\CW(r, p, q)$.

\indent $\CC2$. $\CCW(p, q, r)eqv\CW(q, p, r)$.

\indent $\CC3$. $\lnot\Col(p, q, r)eqv\CCW(p, q, r)\or\CW(p, q, r)$.

The predicates $\CCW$, $\Col$ and $\CW$ for three points $p, q$, and $r$ can be evaluated by testing whether the following 
determinant
$$\eqalign{
 \Det(p, q, r)=
  \hbox{\vrule\hskip2pt$\vcenter{
   \halign{\ctr{$ # $}\quad\ctr{$ # $}\quad\ctr{$ # $}\cr
    x
py
p1\cr
    x
qy
q1\cr
    x
ry
r1\cr}}$\hskip2pt\vrule}\cr\vsk6
 \null=
  \hbox{\vrule\hskip2pt$\vcenter{
   \halign{\ctr{$ # $}\quad\ctr{$ # $}\quad\ctr{$ # $}\cr
    x
py
p1\cr
    x
q-x
py
q-y
p0\cr
    x
r-x
py
r-y
p0\cr}}$\hskip2pt\vrule}\cr\vsk6
 \null=
  (x
q-x
p)(y
r-y
p)-(x
r-x
p)(y
q-y
p)\cr}
\eqno(\Eqii)$$
is positive, zero or negative, respectively. This determinant gives the $z$-coordinate of the vector product $(q-p)\times(r-p)$. If 
$\alpha$ is the angle between these two vectors, then the determinant gives $\leftv q-p\rightv \leftv r-p\rightv \sin \alpha$, so 
the result is nonzero only if the three points are not on the same line, and is positive if and only if the angle $\alpha$ is in 
$(0\deg\sp 180\deg)$\footfig3cm\dag{We may also recall that the absolute value of the determinant (\Eqii) is twice the area of the 
triangle $pqr$, i.e. the area of the parallelogram having the vectors $q-p$ and $r-p$ as adjacent sides.}.

\mfig 4cm
The coding of a sequential search for the first $i$ such that $\CCW(c, p, v
{i+1})$ is complicated by the circular nature of the 
standard representation. Say we begin by testing $\CCW(c, p, v
1)$, and find it to be true; can we conclude $[s
0\to s
0\pr)$ is 
the move that intercepts $r$? clearly not; the correct $i$ may be any index except $1$.
\endmfig

\mfig 7cm
There are many ways to take care of this problem; perhaps the most practical is to use the first vertex $v
0$ as the reference 
point $c$. Even though $v
0$ is not interior to th epolygon, the discussion above carries through almost unchanged. The main 
difference is that the ray $r$ may also contain an entire edge of the polygon (either $[v
0\sp v
1]$ or $[v
{n-1}\sp v
0]$), or 
miss all edges. The advantage of this trick is that all rays from $c=v
0$ that meet the boundary of $P$ span less than half of the 
circle of directions; they are all to the left of $cv
1$ and to the right of $cv
{n-1}$. The vertices $v
1, v
2, \ldots, v
n$ still 
occur in counterclockwise (or clockwise) order as seen from $v
0$, as from any interior point of $P$.
\endmfig

Therefore, if $\CCW(v
0, p, v
1)$ or $\CCW(v
0, v
{n-1}, p)$ then we know $p$ is outside the polygon. If $\Col(v
0, p, v
1)$ then 
we have to test whether $p$ is in $[v
0\sp v
1]$ or not, and accordingly report whether $p$ is on the boundary or outside the 
polygon. If $\Col(v
0, p, v
{n-1})$ we proceed in a similar fashion.

Otherwise we perform a simple linear search starting with $i=1$ for the first $i$ such that $\CCW(c, p, v
{i+1})$. This locates the 
move $[s
i\to s
i\pr)$ that intercepts the ray $r$. Then we can report that $p$ is inside $P$, outside $P$, or on its boundary, 
depending on whether the triangle $pv
iv
{i+1}$ is counterclockwise, degenrate or clockwise; that is, whether $\Det(p, v
i, v
i+1)$ 
is positive, zero or negative. 

This algorithm is still linear in $n$, but now it should be clear how to improve its asymptotic time bound: since the rays $cv
i$ 
are linearly ordered by the $\CCW$ predicate, we can use binary search to locate $cp$ between two of them. This allows us to locate 
a point in a convex polygon using only $\lg n+O(1)$ evaluations of the $\CCW$ test.

This algorithm (like any decent one) returns not only the ``inside/outside'' answer, but also a proof of its correctness: if $p$ is 
inside, we get a triangle $v
0v
iv
{i+1}$ with vertices on $P$ that contains $p$; if $p$ is outside, we get a move $[s
i\to 
s
i\pr)$ whose tangent separates $p$ from $P$; and, finally, if $p$ is on the boundary we get the edge that contains it.

\subsection {10.4.2. Point location in a monotone polygon}

\mfig 5cm
A {\it polygonal chain} is a portion of a polygonal tour, i.e. is an alternating sequence of moves and turns such that the final 
state of each element is the inital state of the following one. A polygonal chain does not have to be closed, but (unless said 
otherwise) we will assume it begins and ends witha move. That is, we can write such a chain as a sequence of states $C=\langle 
s
0\,s
0\pr\,s
1\, s
1\pr\, \ldots\, s
{m-1}\,s
{m-1}\pr\rangle$ such that, for all relevant $i$, $[s
i\pr\to s
{i+1})$ is a turn 
and $[s
i\to s
i\pr)$ is a move. Like we did for tours, we will often consider the chain $C$ as a continuous function that for each 
``instant'' $t\in[0\sp m-{1\over2})$ gives a state $C(t)$.
\endmfig

A polygonal chain is said to be {\it monotone} with respect to some direction $d$ if its moves are all forward or all backward, and 
they all move to the left of $d$.
\figspace 3cm

\mfig 8cm
Let $P$ be a standard convex polygon, and $d$ an arbitrary direction. The orientations of the moves of $P$ are cyclically ordered 
in $S
1$. Those moves that are oriented to the left of $d$ occur in consecutive positions along $P$; therefore, they (plus the 
intervening turns) constitute a polygonal chain that is monotone with respect to $d$. An analogous statement is true for the moves 
oriented to the right of $d$: they constitute a monotone chain with respect to $-d$.

For simplicity, let's assume $d$ is parallel to the $x$-axis. Then we can break the boundary of $P$ in two disjoint chains, 
respectively monotone with respect to $d$ and $-d$; that is, one chain always moves in the general ``up'' direction, and the other 
always ``down''. These chains are connected by two ``joints'', each consisting of either a single turn or two turns and an 
horizontal move.
\endmfig

These two chains define two infinite convex regions, the {\it left shadow} $P
L$ and the {\it right shadow} $P
R$ of $P$, whose 
intersection is $P$. The point $p$ is in $P
L$ if it lies to the left of some point of $P$, i.e. to the left of the rightmost of 
the two chains; and similarly for $P
R$. Therefore, $p$ lies in $P$ if it is to the left of the chain $C
L$ bounding $P
L$, and to 
the right of the chain $C
R$ bounding $P
R$.
\figspace 3cm

\mfig 5cm
If a chain $C$ with $m$ moves is monotone with respect to the direction of the $x$-axis, then a horizontal line will either miss 
$C$ entirely, or pass through $\po s
m$, or intercept a single move of $C$. The last case happens if and only if the line passes 
below $s
m$ but not below $s
0$. Therefore, to decide whether $p$ lies to the left or to the right of $C$, we can locate the move 
$[s
i\to s
i\pr)$ intercepted by the horizontal line passing through $p$, and test whether $p$ is to the left or to the right of 
that move. The index $i$ can be found by binary search, since the vertices $\po s
i$ occur in order of increasing $y$-coordinate.
\endmfig

This procedure can be used to test for point inclusion in any polygonal tour $P$ which can be described as the region between two 
monotone chains, i.e. the intersection of a ``$d$-shadow'' with a ``$(-d)$-shadow''. Such tours are called {\it monotone polygons}; 
they can be characterized as the tracings  in which the car always moves forwards, and faces exactly once towards $d$  and once 
towards $-d$. From a more classical viewpoint, a monotone polygon can be defined by the property that any line parallel to $d$ that 
meets its interior meets exactly two points of its boundary.
\figspace 4cm

We will give here the detailed algorithm, since it will be used in many other occasions: 

\algorithm{\Algi}{Testing a point against a monotone chain.}
\algbody{
  \comm{(We are given a point $p=(x, y)$ and an $x$-monotone
    chain with vertices $v
i=(x
i, y
i)=\po s
i=\po s
i\pr$,
    ordered by increasing $y$-coordinate. The algorithm tests
    whether $p$ is above, below, to the left of, or to
    the right of the chain.)}
  \step{1}{If $y<y
0$ stop and report that $p$ is below
    the chain. Similarly, if $y>y
n$ stop: $p$ is above the chain.}
  \step{2}{ Set $i\gets 0$, $j\gets n$.}
  \step{3}{{\small (At this point we know that
    $y
i\leq y\leq y
j$.)} While $j-i>1$, repeat the following step:}
    \begblock
      \step{4}{Let $k\gets \lfloor (i+j)/2\rfloor$.
        If $y<y
k$, set $j\gets k$; else set $i\gets k$.}
    \endblock
  \step{5}{{\small (Now we know that $y\in [y
i\sp y
{i+1}]$.)}
    Report that $p$ is to the left, on, or to the right of the
    chain depending on whether $\Det(p, v
i, v
{i+1})$ is
    positive, zero or negative (i.e., whether the point $p$
    is to the left, on or to the right of the segment $[v
i\sp v
{i+1}]$.}
 }
 
In the computer, a monotone chain can be represented by an array $\prg{s}$ containing the $m+1$ vertices of the chain, 
$\prg{s[$i$]}=\po s
i=\po s
i\pr$ for $0\leq i\leq m$. We can make for monotone chains the same observations we made for convex 
polygons, regarding the use of linked structures for their representation.

Note that binary search techniques (like algorithm {\Algi}, or the polar version discussed before) can be used as given only if the 
polygon is represented as a linear array of vertices, because of the ``random'' order in which the elements are accessed. If the 
vertices are stored in cyclical order in a balanced binary tree, it is still possible to do binary search by exploiting the 
structure of the tree. If the polygon is represented as a linked list of vertices, then binary search is ruled out.

A feature of algorithm {\Algi} is that all but one of its tests are simple coordinate comparisons. The only exception is the final 
test in step 5, which is a {\it quadratic test}, i.e. a test for the sign of a second-degree function of the input coordinates $x$, 
$y$, $x
i$, and $y
i$. The number of coordinate tests (including those in step 1) is at most $\lfloor\lg m+2\rfloor$, so this 
algoritm is indeed quite fast.

It may be natural to ask whether there is an algorithm for point inclusion in a convex or monotone polygon that uses only $O(\log 
n)$ coordinate comparisons, without any other kinds of tests involving the input arguments. The answer is no: there is no finite 
algorithm for point inclusion that uses only coordinate comparisons as its basic tests.  Indeed, we can't get a finite algorithm 
even if we allow comparisons between arbitrary linear functions of the input coordinates.

We leave to the reader the details of how to test for point inclusion in a convex polygon $P$ using two calls on algorithm {\Algi} 
(perhaps modified to account for different $d$s), plus some extra tests to distinguish the case when $p$ is inside $P$ from the 
case when it lies on some horizontal edge at the top or bottom of $P$. Like its polar counterparts, this point inclusion algorithm 
gives not only the general location of the point (inside/outside/on the boundary), but also a ``proof'' of its correctness. If the 
point is inside, we get a pair of edges such that $p$ is to the left of one and to the right of the other; if $p$ is outside, we 
get an edge whose supporting line separates $p$ from the polygon; and finally, if $p$ is on the boundary, we get an edge that 
passes through or terminates on it.

\subsection{10.4.3. Extremal points of a convex polygon}

Algorithm {\Algi} is an efficient algorithm for point inclusion in a convex polygon $P$, provided we have the decomposition of $P$ 
into left and right shadows. Even if we assume the decomposition to be part of the data structure for $P$, it is quite likely that 
at some point we will have to compute it from the cyclic list of vertices.

To find this decomposition, we have to locate the vertices of largest and smallest $y$-coordinate, which are also the turns of $P$ 
where the the car becomes parallel or opposite to the $x$-axis. In the general case, we want the turns where the car faces parallel 
and opposite to a given direction $d$, and this corresponds to finding the points of $P$ where the signed distance from the car to 
a line parallel to $d$ assumes its maximum and minimum values. If we discard the turns corresponding to these two extremal 
vertices, the rest of $P$ breaks in two monotone chains\foot\dag{There may be two distinct vertices at the same maximum distance 
from the line; in this case both turns and the move connecting them should be discarded. A similar observation holds for the 
vertices at minimum distance.}. These extremal vertices can be found by a straightforward enumeration of all vertices. This 
algorithm is very easy to code, and runs in $O(n)$ time for any reasonable representation of polygons.

The idea of using some sort of binary search to locate those extremal vertices comes most naturally. The idea is basically as 
follows. Let $P$ be a standard convex polygon and $d$ be the direction of the $x$-axis. Supppose we know that the instant when that 
polygon attains maximum $y$-coordinate, and therefore the car is horizontal, lies in the interval $[a\sp b]$. We take the midpoint 
$c$ of that interval, and test the state $P(c)$. If $P(c)$ is facing up, then $c$ is before the maximum, and we must replace our 
interval by $[c\sp b]$. If $P(c)$ is facing down, then we have passed the maximum and we should take now the interval $[a\sp c]$. 
After $O(\log n)$ iterations, the interval of uncertainty will contain a single turn or move, and we can stop.
\figspace 3cm

A closer scrutiny quickly reveals a serious flaw in this idea, brought about by the cyclical nature of polygons. The method works 
indeed if $P(a)$ and $P(b)$ are oriented respectively up and down; the problem is how do we get such a pair of instants. Taking 
$a=0$ and $b=n\over 2$ or vice-versa may not work, since the number of ``up'' moves may be different from that of ``down'' moves, 
and both instants may turn out to be of the same kind. Indeed, there may be only one ``up'' move in $P$; to find $a$ and $b$ with 
the desired property, we have to locate that move. If we allow only tests of the type ``is $P(t)$ oriented upwards'', then clearly 
we may have to perform $O(n)$ tests in the worst case.

Clearly, in order to find the extremal points of a polygon through binary search we need more powerful tests. One solution requires 
us to test not only whether $P(t)$ is oriented up or down, but also whether a state $P(t
1)$ is oriented to the left or to the 
right of another state $P(t
2)$. Using $O(\log n)$ of these tests, it is possible to find two states $P(a)$ and $P(b)$ with 
opposite orientations, which serve as starting points for the standard bisection algorithm above.

A simpler solution uses only tests of the form ``is $P(t
1)$ above $P(t
2)$'', and locates the extremal points directly, by a 
modified form of bisection search. The method is based on the fact that the ordinate $y(t)$ of $P(t)$ is a {\it periodic unimodal} 
function of $t$, i.e. a continuous and periodic function that has a unique local maximum in each period. This condition is 
equivalent to having a single local minimum in each perod\foot\dag{To be precise, $y(t)$ has always infinitely many local maxima, 
but they are all clustered together in a single ``plateau'', corresponding to one turn or to one move and two adjacent turns. The 
same applies to the local minima.}.

This second solution has the advantage that it applies to $x$-monotone polygons in general, while the first  is valid only for 
convex ones. Indeed, the algorithm given below may be considered as solving a problem of numerical analysis. The algorithm is based 
on the following key property of any periodic unimodal function $f$: if $a<c<b$ and $f(a)\leq f(c)\geq f(b)$, then there is a local 
maximum of $f$ in the interval $(a\sp b)$. 

\algorithm{\Algii}{Maximum of a periodic unimodal function.}
\algbody{
   \comm{Given a periodic unimodal function $f$ with period
     $n$, finds within a given tolerance an instant
     when it attains its maximum value.}
   \step{1}{Set $a\gets 0, b\gets n, c\gets n/2$.}
   \step{2}{While $f(c)<f(a)$ or $f(c)<f(b)$, set $t\gets
     a, a\gets c, c\gets b, b\gets t+n$.}
   \step{3}{{\small Now $a<c<b$ and $f(a)\leq f(c)\geq f(b)$,
     so there is a maximum of $f$ in that interval.}\hfil\null\penalty-2000
     While $\leftv a-b\rightv$ is greater than the required tolerance,
     repeat the following steps:}
     \begblock
       \step{4}{If $c-a>b-c$, set $d\gets c$ and $c\gets (a+d)/2$;
         otherwise, set $d\gets (b+c)/2$.}
       \comm{Now $a<c<d<b$ and $f(a)<\max\set{f(c), f(d)}>f(b)$.}
       \step{5}{If $f(c)>f(d)$ then set $b\gets d$; else set $a\gets c$
         and $c\gets d$.}
       \comm {This eliminates at least ${1\over4}$ of the interval
         $[a\sp b)$.}
     \endblock
   \step{6}{Stop: the maximum is in the interval $[a\sp b)$.}
 }
 
The loop in step 2 eventually terminates, since after at most two permutations the maximum of $f(a)$, $f(b)$ and $f(c)$ will be 
$f(c)$. It is easy to see that the assignments in step 5 preserve the invariant  of step 3. The figure below ilustrates those 
assignments for two typical cases.
\figspace 3cm

To find the points of a convex polygon at maximum and minimum distance from a line $\lscr$, we may take $f(t)$ to be the dot 
product of the position $\po P(t)$ with a vector $d\pr$ perpendicular to $\lscr$ and pointing to its left. In the case when $\lscr$ 
is the $x$-axis, of course, $f(t)$ is simply the $y$-coordinate of $\po P(t)$. Since we know that maximum and minimum of $f(t)$ is 
attained at a vertex, we can restrict the search to integer instants only, and stop whenever the error is less than $1$.

It may be instructive to consider in detail how would we code algorithm {\Algii} with the above changes. The program we show next 
is written in a fictitious Algol-like language, that should be readable without much difficulty by anyone conversant in PASCAL or 
ALGOL. Note the use of $\prg{mod}$ in the indexing of the matrix $v$. The given function $f(p)$ should compute the signed distance 
from the point $p$ to the desired line, or the dot product of $p$ with the perpendicular direction vector $d\pr$. 

\vskip10pt plus10pt

{\prog
Find-Maximum: procedure with arguments
     (v: array[0..n) of point,
      f: function from (p:point) into real) =
      
begin
    a: integer \pgets 0;
    b: integer \pgets n;
    c: integer \pgets (a + b)/2;
    
while f(v[c mod n]) < f(v[a mod n])  or  f(v[c mod n]) < f(v[b mod n]) do
      t \pgets a; a \pgets c; c \pgets b; b \pgets t+n
      od;
      
while b - a > 1 do

if b - c > c - a  then  d \pgets (b + c)/2
        else  d \pgets c; c \pgets (a + d + 1)/2
        fi;
        
if f(v[d mod n]) > f(v[c mod n]) then b \pgets c
        else a \pgets c; c \pgets d
        fi
        
od
   end.
\endprog}

Algorithm {\Algii} gives us also a method for testing whether a line $\lscr$ intersects a convex polygon $P$. All we have to do is 
to find the vertices of $P$ with maximum and minimum signed distance from $\lscr$; then the latter will intercept $P$ if and only 
if these distances have opposite signs, i.e if and only if the two extrema are on opposite sides of $\lscr$. If that is the case, 
they are a proof that $\lscr$ meets the interior of $P$. If both extrema lie on the same side of $\lscr$, then the tangent to $P$ 
parallel to $\lscr$ and passing through the extremum that is closest to $\lscr$ separates it from $P$.
\figspace 3cm

\section{10.5. Polygon intersection via convolution}


We will now apply our convolution machinery to the development of an algorithm for testing convex polygon intersection. Several 
further examples of the use of convolutions in computational geometry problems will be given later on in the notes. As we already 
remarked, the fundamental theorem tells us that two convex polygons $P$ and $Q$ intersect, if and only if the origin is inside 
$P\ast Q^{-I}$. Let $p$ and $q$ denote the sizes of $P$ and $Q$ respectively. We already know how to build the convolution in time 
$O(p+q)$, and to test for point inclusion in the result in time $O(\lg (p+q))$; it follows that we can test for the intersection of 
$P$ and $Q$ in time $O(p+q)$. There may be a temptation to rest on our laurels at this point, since, after all, don't we have to 
look at each edge of $P$ and $Q$ to know if they intersect? Suprisingly, the answer is no. We will see how, by the clever use of 
binary search ideas, we can test for intersection in time only $O(\lg (p+q)) = O(\lg p + \lg q)$ (why are these equal?) using the 
standard representations for $P$ and $Q$.

Before we proceed towards this goal, let us remark that there are applications where $P$ and $Q$ may be freely movable around the 
plane by translation, and for each placement of $P$ and $Q$ we may want to know whether they intersect. This is the case, for 
example, when $P$ and $Q$ represent solid bodies moving around on the plane. (Although we have not discussed this, the same ideas 
work in three-dimensional space as well, where this collision avoidance problem is very important.) Now for this situation the 
above solution is exactly what we want: $P^x$ will intersect $Q^y$ iff $O\in P^x\ast (Q^y)^{-I} = P^x\ast Q^{-I-y}$. But the latter 
inclusion is equivalent to $y-x\in P\ast Q^{-I}$. So, after computing the convolution $P\ast Q^{-I}$ just once, in time $O(p+q)$, 
we can test for intersection in logarithmic time for each placement of $P$ and $Q$.
\figspace 4cm

The central idea in the more efficient algorithms we are about to describe is that we don't need to compute the entire convolution 
in order to test for point inclusion against it. Rather, we will emulate a point inclusion algorithm while computing the parts of 
the convolution that we need to test against only if we need to. It is important to understand this general strategy, as it is 
applicable to problems other than the one we are currently discussing, such as common tangent computations, distance determination, 
etc.

Suppose, for example, that we desire to test on what side of the move $e$ of $P\ast Q^{-I}$ the origin lies. Suppose further that 
we know that $e$ comes from edge $f$ of $P$. As we know, $e$ is then the vector sum $f+v$ for some vertex $v$ of $Q$. If can 
determine $v$, then we can place $e$ in the same position in the plane it will occupy in the convolution. Since the latter will be 
a frequent operation, we will call it ``placing $e$ in the convolution''. To find $v$, we simply have locate $e$ according to slope 
in the edge cycle of $Q$. We already know how to do this by binary search in time $O(\lg q)$, as in section 10.4.3. Thus we can 
place an edge in the convolution and test a point against it in total time only $O(\max\set{\lg p,\lg q}) = O(\lg(p+q))$.

For the pragmatic reasons enumerated earlier, we choose to emulate the cartesian point inclusion algorithm. Recall that this 
algorithm is based on discriminating a point against a monotone chain. For a convex polygon $P$, we defined its left ($P
{L}$) and 
right ($P
{R}$) shadows and showed that $p\in P$ if and only if $p\in P
{L}$ and $p\in P
{R}$. The relationship between shadows and 
intersection is given by the following lemma.

\lemma{\Thexviii}{The intersection $P\inte Q$ is non-empty if and only if both intersections $P
{L}\inte Q
{R}$ and $P
{R}\inte 
Q
{L}$ are non-empty.}

\proof{In one direction the lemma is clear. A point $x$ belonging to both $P$ and $Q$ belongs to all four of $P
{L}, P
{R}, Q
{L},$ 
and $Q
{R}$. To prove the converse, suppose that $P$ and $Q$ are disjoint. By lemma 3.18 we know that they possess a separating 
line $\lscr$. If $\lscr$ is horizontal, then clearly both $P
{L}\inte Q
{R}$ and $P
{R}\inte Q
{L}$ are empty. If not, let $P$ be 
the polygon to its left, and $Q$ the one to its right. Obviously $P
{L}\inte Q
{R} = \empty$ and we are done.}

Thus it suffices to be able to test the intersection of a left shadow $L$ with a right shadow $R$. By the convolution theorem this 
is equivalent to testing whether the origin belongs to $L\ast R^{-I}$. Note that $R^{-I}$ is a {\it left} shadow, and that the 
convolution of two left shadows is also a left shadow. This is then the problem we will consider: given two left shadows $A$ and 
$B$, discriminate the origin against $A\ast B$. We assume that each of $A$ and $B$ is given to us as an array containing the 
coordinates of its vertices and arranged in decreasing $y$ order.

To follow now the suggestion given above, we wish to emulate the process of point discrimination against a monotone chain 
(algorithm 1) by running it on the implicitly known monotone chain $A\ast B$. Let $a$ and $b$ denote respectively the sizes of $A$ 
and $B$, and let $n=a+b$. The first step of this algorithm is to discriminate the origin against the median edge of $A\ast B$. When 
we know a chain explicitly, finding its median edge is a constant time operation. But how do we find the median edge of $A\ast B$? 
It is actually possible to find which edge of $A$ or $B$ would be the median edge of the convolution in $O(\lg n)$ tests, but we 
leave this as an exercise for the reader.

The reason we wish to discriminate against the middle edge of $A\ast B$ is that it allows us to eliminate at least half the edges 
of the convolution after an edge comparison. The logarithmic time bound of the discrimination algorithm, however, depends only on 
being able to eliminate some fixed fraction of the edges after each comparison, so we can afford to be less demanding. If we assume 
without loss of generality that $a\geq b$, then a discrimination against the middle edge of $A$ in the convolution will allow us to 
get rid of at least half the edges of $A$, or a quarter of the total. To do this discrimination, we must place this edge in the 
convolution, or equivalently, locate it according to its slope in the list of edges of $B$. A binary search will do this in $O(\lg 
n)$ time. This implies that we can run an emulation of algorithm 1 in $O(\lg n)$ stages of cost $O(\lg n)$ each, or total cost 
$O(\lg^2 n)$.

Is this the best we can do? We will show that we can actually discriminate the origin against the convolution $A\ast B$ in time 
only $O(\lg n)$. To this end let us first look at another restatement of the definition of convolution:

\lemma{\Thexix}{Let $A$ and $B$ be two left shadows bounded on the right by two $y$-monotone chains with high endpoints $h
A$, 
$l
A$ and low endpoints $h
B$, $l
B$ respectively. Each interleaving of the edges of $A$ and $B$ can be viewed as a monotone chain 
from $h
A+h
B$ to $l
A+l
B$. Among all these chains the convolution $A\ast B$ is the righmost one, in the sense that no other 
interleaving extends at any $y$ value further to the right than the convolution.}

\proof{It will be instructive to consider the following argument. Consider any arbitrary interleaving of the edges of $A$ and $B$, 
as shown below, defining a chain $C$.
\figspace 4cm

\pp Suppose there are two consecutive  edges $e$ and $f$, such that they are out of order in slope. Then $e$ and $f$ cannot both 
belong to $A$ or $B$, so without loss of generality let us assume that $e$ belongs to $A$ and $f$ belongs to $B$. Now consider the 
chain $D$ obtained by swapping the order of $e$ and $f$ in $C$. Then clearly $D$ is everywhere to the right of $C$, and it has one 
less pair of edges out of slope order. We can keep applying this transformation till no pair of adjacent edges is out of order. The 
resulting chain will be the convolution $A\ast B$, and it will be to the right of all other chains.}

\mfig 6cm
For the faster algorithm we cannot afford to spend time $O(\lg n)$ in placing an edge of the convolution. Instead we wish to find a 
constant time test that allows us to get rid of some fraction of the edges of $A$ or $B$. Let $e$ denote the median edge of $A$, 
and $f$ the median edge of $B$. Again, without loss of generality, we can assume that $e$ precedes $f$ in slope. Let also $A
H$, 
$A
L$, $B
H$, $B
L$ denote respectively the high and low halves of $A$ and $B$ obtained after edges $e$ and $f$ are removed. 
Consider now the chain $D$ which is the concatenation of $A
H\ast B
H$ with $e$, $f$, and $A
L\ast B
L$ in this order. We can place 
$e$ and $f$ in $D$ in constant time. In the convolution $C$ the edges $e$ and $f$ must occur as shown at right.
\endmfig

Consider now the partition of the plane define by edges $e$ and $f$ as shown below.
\figspace 4cm
If the origin $O$ falls in region {\it Left}, then clearly $O$ is to the left of the convolution, and we are finished. If $O$ falls 
in region {\it Above}, then what can we conclude? In discriminating against the convolution, all edges of $B
L$ will be below $O$, 
so they can be discarded without affecting the outcome of the discrimination. Similarly, if $O$ falls in region {\it Below}, then 
$O$ will be below all edges of $A
H$ in the convolution, so these edges can be discarded. Therefore by this constant time test we 
have been able to reduce ourselves to an equivalent problem where either chain $A$, or chain $B$, has been halved.

After $O(\lg a)+O(\lg b) = O(\lg n)$ such steps the upper or lower half of either $A$ or $B$ must become empty, so at that point 
one of $A$ or $B$ has no more than two edges left. It is now possible to complete the discrimination in $O(\lg n)$ further time. 
For suppose that it is $B$ that has been reduced to one or two edges. The location of these edges of $B$ among the slope ordering 
of the edges of $A$ can be computed in $O(\lg n)$ steps. Once that is done, we can discriminate $O$ against all the edges of $A$, 
as they appear in the convolution, in total time $O(\lg n)$, since we can now place each edge of $A$ in the convolution in constant 
time. To complete the discrimination we may at most need to test against the one or two remaining edges of $B$. Thus we have been 
able to discriminate $O$ against $A\ast B$ in total cost $O(\lg n)$. So we have proved:

\theorem{\Thexx}{It is possible to discriminate a point $p$ against the convolution of two left shadows of size $O(n)$ in time 
$O(\lg n)$.}

\theorem{\Thexxi}{It is possible to test if two convex tracings of size $O(n)$ intersect in total time $O(\lg n)$.}

The last result, as stated, is somewhat unsatisfactory, since we may want to know more than whether our two convex tracings $P$ and 
$Q$ intersect. For example, we may want to know of a common point if they do intersect, or a separating line if don't. The point, 
or line, respectively are {\it witnesses} to the intersection, or non-intersection, of $P$ and $Q$. On the other hand it is not 
reasonable to expect the same algorithm to produce the complete description of the intersection $P\inte Q$ and stay witin the 
$O(\lg n)$ time bound, since, as we will shortly see, this decription can take $O(p+q) = O(n)$ space to write down.

Suppose first that the algorithm responds that $P$ and $Q$ do not intersect, and let as before $P
{L}$, $P
{R}$, $Q
{L}$, $Q
{R}$ 
denote the left and right shadows of $P$ and $Q$ respectively. Then at some comparison it was discovered that $O$ lies above both 
$P$ and $Q$, or below both $P$ and $Q$, or to the left of $P
R\ast Q
L^{-I}$, or to the right of $P
L\ast Q
R^{-I}$. All four cases 
are essentially analogous, so let us suppose that some edge test showed $O$ to be to the right of the convolution of $P
L$ and 
$Q
R^{-I}$. That in fact was a test against some edge $e$ of either $P$ or $Q$.

\mfig 6cm
Let $v$ be the point where $e$ intersects the negative $y$ axis. Point $v$ must be of the form $p-q$, where $p$ is a point of the 
boundary of $P
L$ and $q$ is a point of the boundary of $Q
R^{-I}$. (Furthermore, $p$ and $q$ can be computed from $v$ in constant 
time). There is a line $\lscr$ parallel to $e$ and separating $O$ from $P
L\ast Q
R^{-I}$, for example the line through the point 
$(p-q)/2$. It is easy to check that $\lscr$, translated by $q$, is in fact a separating line of $P$ and $Q$. We have now in fact 
rederived lemma 3.18 proved earlier, namely that two disjoint convex polygons in the plane have a separating line parallel to a 
side of one of them.
\endmfig

\vfill\eject

It is also interesting to do the same when $P$ and $Q$ do intersect. Then our algorithm establishes that $O$ is to the left of 
$P
L\ast Q
R^{-I}$ by some edge test against an edge $e$. The point where $e$ intersects the $x$ axis is of the form $p
e-q
e$, and 
it is easy to check that this implies that the line segment from $q
e$ on the left to $p
e$ on the right is in $P
L\inte Q
R$. 
Similarly, $O$ is shown to be to the right of $P
R\ast Q
L^{-I}$ via an edge test against some edge $f$. This now leads to a line 
segment from $p
f$ on the left to $q
f$ on the right that is in $P
R\inte Q
L$. We leave it to the reader to show that the segments 
$p
ep
f$ and $q
eq
f$ do in fact intersect, and that their intersection point is a point in $P\inte Q$.
\figspace 4cm

\par\vfill\eject

\section{JUNK:}

\subsection {Common tangents}

[ ]  tangents from a point to a polygon; linear algorithm
discuss bimodality of intercept on separator

[ ]  distance between antipodal (= opposite?) tangents

[ ]  maximally apart antipodal tangents
    a. touch the polygon exactly once each
    b. line joining points of contact is perpendicular to the tangents
    c. length of that segment equals the diameter of the set
    
[ ]  same true for minimally apart antipodal tangents

[ ]  two disjoint convex polygons P and Q; consider antipodal tangents, one to P and one to Q

[ ]  if (p,q) is the distance from P to Q, then the tangents at p and q are antipodal and are perpendicular to P and Q

[ ]      a. disjoint convex sets have a separating line
    b. even one parallel to a side of one of them (Hobby argument)
    
[ ]  Take two disjoint convex polygons and wlog rotate the plane so that their separating line is vertical

[ ]  Use car language; discuss states at leftmost and rightmost points

[ ]  existence of exactly two outer common tangents by intecept on separator argument
existence of exactly two inner common tangents

[ ]  computing the outer common tangents; **give clean linear algorithm and proof

[ ]  give $log^2$ algorithm based on separator intercept
give log algorithm based on predicates
    RA: A is to the right of b
    RB: B is to the right of a
    and cutting up the product space
discuss L-shape binary search in detail with invariants maintained

[ ]  new observation that eliminates L-search

[ ]  remark on always following rightmost car; prove that when we switch from one tracing to the next, the car moves forwards. Thus 
result is a convex tracing, the convex hull.

[ ]  discuss leftmost car; concept of monostrofic (??) tracing. Remark that common tangent computation algorithms apply also to 
monostrofic tracings.

[ ]  derive Jarvis's algorithm for CH from same ideas on n cars spinning on n points.

[ ]  delop carefully log search algorithm for bimodal function zero crossings, or maxima and minima
apply to get log algorithm for tangents

\par\vfill\eject\end