[Cyan]<PreISLCedar>Stolfi>GBOld>GBb10C.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\Thexix{19}
\def\Thexx{20}
\def\Thexxi{21}
\def\Thexxii{22}
\def\Thexxiii{23}
\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\Defi{1}
\def\The{\bug}

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

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.

\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} = \ety$ 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 $hǍ$, $lǍ$ and low endpoints $hB̌$, $lB̌$ respectively. Each interleaving of the edges of $A$ and $B$ can be viewed as a monotone chain from $hǍ+hB̌$ to $lǍ+lB̌$. 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.}

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

\mfig6
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 $AȞ$, $AĽ$, $BȞ$, $BĽ$ 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 $AȞ\ast BȞ$ with $e$, $f$, and $AĽ\ast BĽ$ 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.\fig4
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 $BĽ$ 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 $AȞ$ 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:

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 $PŘ\ast QĽ↑{-I}$, or to the right of $PĽ\ast QŘ↑{-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 $PĽ$ and $QŘ↑{-I}$. That in fact was a test against some edge $e$ of either $P$ or $Q$.

\mfig6
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 $PĽ$ and $q$ is a point of the boundary of $QŘ↑{-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 $PĽ\ast QŘ↑{-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

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 $PĽ\ast QŘ↑{-I}$ by some edge test against an edge $e$. The point where $e$ intersects the $x$ axis is of the form $pě-qě$, and it is easy to check that this implies that the line segment from $qě$ on the left to $pě$ on the right is in $PĽ\inte QŘ$. Similarly, $O$ is shown to be to the right of $PŘ\ast QĽ↑{-I}$ via an edge test against some edge $f$. This now leads to a line segment from $pf̌$ on the left to $qf̌$ on the right that is in $PŘ\inte QĽ$. We leave it to the reader to show that the segments $pěpf̌$ and $qěqf̌$ do in fact intersect, and that their intersection point is a point in $P\inte Q$.\fig4