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

\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\Eqii{2}
\def\Eqiii{3}
\def\Algi{1}
\def\Algii{2}
\def\PP{{\char P}}
\def\CC{{\char C}}
\def\CW{\mathop{\char C\char W}}
\def\Col{\mathop{\char C\char o\char l}}
\def\Det{\mathop{\char D\char e\char t}}
\def\Defi{1}
\def\The{\bug}

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

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

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

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

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

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

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 $m1̌$ and $m2̌$ of $P$ all those moves of $Q$ whose orientation lies in the arc $(\stdir m1̌\span \stdir m2̌)$. 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.

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.

\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 s0̌\,s0̌\pr\,s1̌\,s1̌\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$]}=\stpos sǐ=\stpos sǐ\pr$, in the order in which they are traversed. The orientation of the critical states can be reconstructed from this information: the orientation of $sǐ$ is parallel to the vector from $\prg{s[$i-1$ mod $n$]}$ to $\prg{s[$i$ mod n]}$, and that of $sǐ\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\span 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 $[sǐ\to sǐ\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 $[sǐ\to sǐ\pr)$ is null: we then have $\stpos sǐ=\stpos sǐ\pr=\stpos s{̌i+1}$, so$\prg{s[$i+1$ mod $n$]}$ is superfluous, and can be used to store the direction $\stdir sǐ=\stdir sǐ\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.

\mfig7
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 $[cvǐ\span 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:

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
xp̌|yp̌|1\cr
xq̌|yq̌|1\cr
xř|yř|1\cr}}$\hskip2pt\vrule}\cr\vc
\null|=
\hbox{\vrule\hskip2pt$\vcenter{
\halign{\ctr{$ # $}\quad|\ctr{$ # $}\quad|\ctr{$ # $}\cr
xp̌|yp̌|1\cr
xq̌-xp̌|yq̌-yp̌|0\cr
xř-xp̌|yř-yp̌|0\cr}}$\hskip2pt\vrule}\cr\vc
\null|=
(xq̌-xp̌)(yř-yp̌)-(xř-xp̌)(yq̌-yp̌)\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\span 180\deg)$\footfig\dag(3){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.}.

\mfig4
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, v1̌)$, and find it to be true; can we conclude $[s0̌\to s0̌\pr)$ is the move that intercepts $r$? clearly not; the correct $i$ may be any index except $1$.
\endmfig

\mfig7
There are many ways to take care of this problem; perhaps the most practical is to use the first vertex $v0̌$ as the reference point $c$. Even though $v0̌$ 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 $[v0̌\span v1̌]$ or $[v{̌n-1}\span v0̌]$), or miss all edges. The advantage of this trick is that all rays from $c=v0̌$ that meet the boundary of $P$ span less than half of the circle of directions; they are all to the left of $cv1̌$ and to the right of $cv{̌n-1}$. The vertices $v1̌, v2̌, \ldots, vň$ still occur in counterclockwise (or clockwise) order as seen from $v0̌$, as from any interior point of $P$.
\endmfig

Therefore, if $\CCW(v0̌, p, v1̌)$ or $\CCW(v0̌, v{̌n-1}, p)$ then we know $p$ is outside the polygon. If $\Col(v0̌, p, v1̌)$ then we have to test whether $p$ is in $[v0̌\span v1̌]$ or not, and accordingly report whether $p$ is on the boundary or outside the polygon. If $\Col(v0̌, 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 $[sǐ\to sǐ\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 $pvǐv{̌i+1}$ is counterclockwise, degenrate or clockwise; that is, whether $\Det(p, vǐ, vǐ+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 $cvǐ$ 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 $v0̌vǐv{̌i+1}$ with vertices on $P$ that contains $p$; if $p$ is outside, we get a move $[sǐ\to sǐ\pr)$ whose tangent separates $p$ from $P$; and, finally, if $p$ is on the boundary we get the edge that contains it.

\mfig5
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 s0̌\,s0̌\pr\,s1̌\, s1̌\pr\, \ldots\, s{̌m-1}\,s{̌m-1}\pr\rangle$ such that, for all relevant $i$, $[sǐ\pr\to s{̌i+1})$ is a turn and $[sǐ\to sǐ\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\span m-{1\over2})$ gives a state $C(t)$.
\endmfig

\mfig8
Let $P$ be a standard convex polygon, and $d$ an arbitrary direction. The orientations of the moves of $P$ are cyclically ordered in $S1̌$. 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} $PĽ$ and the {\it right shadow} $PŘ$ of $P$, whose intersection is $P$. The point $p$ is in $PĽ$ 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 $PŘ$. Therefore, $p$ lies in $P$ if it is to the left of the chain $CĽ$ bounding $PĽ$, and to the right of the chain $CŘ$ bounding $PŘ$.\fig3

\mfig5
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 $\stpos sm̌$, or intercept a single move of $C$. The last case happens if and only if the line passes below $sm̌$ but not below $s0̌$. Therefore, to decide whether $p$ lies to the left or to the right of $C$, we can locate the move $[sǐ\to sǐ\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 $\stpos sǐ$ 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.\fig4

\comm{(We are given a point $p=(x, y)$ and an $x$-monotone chain with vertices $vǐ=(xǐ, yǐ)=\stpos sǐ=\stpos sǐ\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{\sno3 {\small (At this point we know that $yǐ\leq y\leq yǰ$.)} While $j-i>1$, repeat the following step:}
\begblock
\step{\sno4 Let $k\gets \lfloor (i+j)/2\rfloor$. If $y<yǩ$, set $j\gets k$; else set $i\gets k$.}
\endblock
\step{\sno5 {\small (Now we know that $y\in [yǐ\span y{̌i+1}]$.)} Report that $p$ is to the left, on, or to the right of the chain depending on whether $\Det(p, vǐ, 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 $[vǐ\span v{̌i+1}]$.}
\endblock}

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$]}=\stpos sǐ=\stpos sǐ\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$, $xǐ$, and $yǐ$. 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\span 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\span b]$. If $P(c)$ is facing down, then we have passed the maximum and we should take now the interval $[a\span c]$. After $O(\log n)$ iterations, the interval of uncertainty will contain a single turn or move, and we can stop.\fig3

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(t1̌)$ is oriented to the left or to the right of another state $P(t2̌)$. 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(t1̌)$ above $P(t2̌)$’’, 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\span b)$.

\algorithm{\Algii}{Maximum of a periodic unimodal function.}{
\begblock
\comm{Given a periodic unimodal function $f$ with period $n$, finds within a given tolerance an instant when it attains its maximum value.}
\step{\sno1 Set $a\gets 0, b\gets n, c\gets n/2$.}
\step{\sno2 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{\sno3 {\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 {\sno4 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 {\sno5 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\span b)$.}
\endblock
\step{\nono Repeat from step 3.}
\step{\sno6 Stop: the maximum is in the interval $[a\span b)$.}
\endblock}

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

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

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