\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.

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

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.

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.}

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.

\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.

\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.

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

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

[ ] 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