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

\input CgHdr.tex
\begfile{CgN4.tex of February 10, 1983 10:15 AM --- Stolfi}
\notesformat
\inputtty % This is your chance to enter \def\printfilestamp{F}

\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\PP{{\char P}}
\def\Defi{1}

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

\mfig4
Let $P$ be the tour $\langle s0̌\,s0̌\pr\,s1̌\,\ldots\,s{̌n-1}\,s{̌n-1}\pr\rangle$; then $P(t)$ is a function with period $n$, such that $P(i)=sǐ$, $P(i+{1\over2})=sǐ\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 $[sǐ\to sǐ\pr)$ and $[sǐ\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$.

\mfig4
Let us define some new terminology. The {\it forward ray} of a state $s$ is the ray with origin $\stpos s$ and extending towards infinity in the direction of $\stdir 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 $\stpos 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$.\fig3

For brevity, we will sometimes use a state $s$ in places where its position $\stpos s$ or its tangent $\sttan 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 $\stpos s$ lies to the left of the line $\sttan 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:\fig3

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 $\stpos P(a)$ and $\stpos P(b)$ are on opposite sides of a line $\lscr$, then there is a moving instant $t\in (a\span b)$ such that $\stpos P(t)$ is on $\lscr$.\fig3}

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

Lemma {\Thei} follows from the fact that the signed distance between $\stpos 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., $\stpos 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.

\mfig6
\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\span 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\span b)$. It is easy to see that in $[a\span b)$ there is a last instant $c$ when $\stpos 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

\mfig5
\lemma{\Theiv}{Let $P$ be a polygonal tour with no right turns. If $a<b$, $\sttan P(a)$ passes through or to the left of a point $p$, and $\sttan P(b)$ passes to the right of $p$, then there is an instant $c\in[a\span 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\span b)$. It is easy to see that in $[a\span b)$ there is a last time $c$ when $\sttan 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 $\stpos 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.\fig3

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

\mfig5
\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\span 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 $\stpos P(a)$. Lemma {\Theiii} gives us a moving state $P(c)$ with $c\in [a\span 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\span 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:

\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 $\stpos P(a)\neq \stpos P(b)$, then there is a turning instant $c\in (a\span b)$ such that $\sttan P(c)$ is parallel to the vector $\stpos P(b)-\stpos P(a)$.}

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

\mfig7
\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 $\stpos P(a)$ to $\stpos 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 $\stpos P(a\pr)$ to a point $\stpos P(b\pr)$ ahead of it.\fig3

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

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

\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 $\stpos T(t)=p$; for any line $\lscr$, there is at most one turn $T$ and one {\it turning} instant $t$ such that $\sttan 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.

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

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

These properties are not independent of each other; indeed, for any polygonal tracing,
{\def\eqq{\;\;\equiv\;\;}
$$ \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:

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

\mfig4
\pp Suppose now a tour of the tracing contained both forward and backward moves; then there would be a forward move $[sǐ\to sǐ\pr)$ followed by a backward one $[s{̌i+1}\to s{̌i+1}\pr)$. But then, for any state $r$ in the intervening turn $(sǐ\pr\to s{̌i+1})$, the tangent $\sttan r$ would pass between the points $\stpos sǐ$ and $\stpos 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 sǐ)$ followed by a right one $[sǐ\pr\to s{̌i+1})$. Since the moves are all done in the same way, the points $\stpos s{̌i-1}$ and $\stpos s{̌i+1}\pr$ would lie on opposite sides of the tangent of the move $[sǐ\to sǐ\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 $r1̌$ and $s1̌$ that peek to the right of $\lscr$, and two others $r2̌$ and $s2̌$ that peek to the left of it, all with distinct positions by $\PP0$.\fig3

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

\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 $\stpos T(a)$ and $\stpos T(b)$.\fig3

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

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

\mfig6
\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 $r1̌$ of $R$ and $s1̌$ of $S$ peeking to the left of $\lscr$, and two others $r2̌$ and $s2̌$ peeking to the right of it. Then a point $x$ on $\lscr$ sufficiently far away in the direction of $\stdir \lscr$ would be to the right of $r1̌$ and $s1̌$ and to the left of $r2̌$ and $s2̌$. 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 $\sttan 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\span s)$ when $P(d)$ is to the left of $\sttan P(s)$ but facing towards it.\fig3

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

\mfig4
\pp Finally, let’s show $\PP0$ holds. Clearly, $\PP3$ forbids two turning instants with same tangent. Suppose there were two moves $[sǐ\to sǐ\pr)$ and $[sǰ\to sǰ\pr)$ passing through the same point $x$. If the tour is moving backwards, then $sǐ\pr$ and $sǰ\pr$ are distinct turning states that face towards point $x$. If the tour moves forward, then the turns ending at $sǐ$ and $sǰ$ 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

\proof{By theorem {\Theviii}, the tracing contains a single tour $\langle s0̌\, s0̌\pr\, s1̌\, s1̌\pr\, \ldots\, s{̌n-1}\, s{̌n-1}\pr\rangle$. The path traversed by the car is the polygon $\s P=\langle \stpos s0̌, \stpos s1̌, \ldots, \stpos s{̌n-1}\rangle$, which is simple because of $\PP0$. If the car always turns counterclockwise, then each move $[sǐ\to sǐ\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.

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.