\begfile{KinFOCS3.tex of September 12, 1983 1:01 pm --- Stolfi}
\section{6. Some uses of convolution in algorithms}
Besides its intrinsic interest, the convolution operation defined in the previous section can be used as a powerful tool for the development of new geometric algorithms. We will see several instances of this in the present section, as well as an illustration of its use in proving a classical geometric theorem. Some of the new algorithms improve on the currently best known asymptotic time bounds for the problems they solve. Our domain in this section will be convex polygon problems including intersection detection, common tangent computations, and distance computations.
As a warm-up problem, let us study the convolution $C = A\ast A↑{N}$, where $A$ is a convex, counterclockwise oriented and directed tracing. An example is shown in figure 6.1. It is easy to see that $C$ is symmetric around the origin $O$ and contains exactly two copies of each edge of $A$, oppositely oriented. From the set-sum interpretation of the convolution we discussed in the previous section, it follows that:
\lemma{6.1}{The diameter of $A$ equals the maximum radius from $O$ to a point of $C$.}
This lemma in effect captures the essence of Shamos' [\Sh] observation that to find the diameter of a convex polygon it suffices to consider all pairs of antipodal points. Thus we have a linear algorithm for computing the diameter of a convex polygon.
We will now see the use of the convolution as a tool for {\it transforming polygon-polygon problems into point-polygon problems}. Let $P$ and $Q$ denote two counterclockwise oriented convex tracings, each with $O(n)$ moves and turns. The following theorem, which is simply a restatement of theorem 5.1 for the convex case, shows how the convolution can be used for intersection detection.
\theorem{6.2}{Convex tracings $P$ and $Q$ intersect if and only if the origin $O$ is inside the convolution $P\ast Q↑N$.}
If $P$ and $Q$ are disjoint, then the next theorem shows how the convolution can be used for distance computations.
\theorem{6.3}{For disjoint convex tracings $P$ and $Q$, $\dist(P,Q) = \dist(O,P\ast Q↑N)$. This is true in any $Lp$ metric.}
The next two theorems (figures 6.2 and 6.3) give similar reductions for common tangent problems.
\theorem{6.4}{If $t$ is a tangent from the origin $O$ to $P\ast Q↑N$ at point $x-y$, with $x$ on $P$ and $y$ on $Q$, then $t+y$ is an inner common tangent of $P$ and $Q$, touching $P$ at $x$ and $Q$ at $y$ respectively.}
Recall that $\op Q$ denotes $Q$ with its orientation reversed. Then we have:
\theorem{6.5}{If $t$ is a tangent from the origin $O$ to $P\ast (\op Q)↑N$ at point $x-y$, with $x$ on $P$ and $y$ on $Q$, then $t+y$ is an outer common tangent of $P$ and $Q$, touching $P$ at $x$ and $Q$ at $y$ respectively.}
These theorems give us obvious algorithms for computing the common tangents of two convex polygons, detecting if they intersect, and computing their distance. We merely apply an appropriate point-polygon algorithm to some convolution of the two polygons. If the convolution is generated explicitly, the running time will be linear in the total number of sides. However, it is possible to solve each of those problems in sublinear (and even logarithmic) running time. The basic idea is to emulate the point-polygon algorithm while computing only those parts of the convolution that the algorithm needs to look at.
Suppose, for example, that as part of the emulation of a point-polygon algorithm, we desire to test on what side of the move $m$ of $P\ast Q↑N$ the origin lies. Suppose further that we know that $m$ comes from edge $e$ of $P$. As we know, $m$ is then the vector sum $e+v$ for some vertex $v$ of $Q$. If we can determine $v$, then we can place $e$ in the same position in the plane it will occupy in the convolution. To find $v$, we simply have to locate $e$ according to slope in the edge list of $Q$. We can do this by binary search in time $O(\lg n)$. Thus we can place an edge in the convolution and test a point against it in total time only $O(\lg n)$. This example illustrates the idea that constant-time tests in a point-polygon algorithm can be implemented via convolution as $O(\lg n)$ time tests in the polygon-polygon case. Since $O(\lg n)$ algorithms for the point-polygon versions of the above four problems are well-known, it follows that, via the convolution transform, we have $O(\lg↑2 n)$ algorithms for the polygon-polygon versions.
By being cleverer, we can actually get $O(\lg n)$ algorithms for all these problems in a uniform way. The idea is, roughly, that we can get valuable information in the situation described above by testing against an edge that is placed by a constant-time computation ``near'' the convolution. The details will be reported elsewhere. Thus we have a different derivation of a result first obtained by Overmars and van Leeuwen [\OvL] for the common tangents and by Chazelle and Dobkin [\CD] for intersection detection. The $O(\lg n)$ algorithm for distance computation is a new result\foot\dag{We have just been informed the Edelsbrunner has independently obtained the same bound.}.
Some of the power of the concepts we have been developing can be seen also from the following derivation of a classical geometric fact. Suppose that $P$ and $Q$ intersect and let $i$ denote the number of edge intersections and $t$ the number of (outer) common tangents of $P$ and $Q$. Then we have
$$\vbox{\halign{\rt{$ # $}\lft{$\null #$}\hskip20pt\rm #\cr
1-{i\over 2} = \dg(P\cdot \op Q)by lemma 4.6\cr
= \wi(O, P\ast (\op Q)↑N)by theorem 5.1\cr
= \dg(P\ast(\op Q)↑N)-\sw(O, P\ast(\op Q)↑N)by theorem 3.4\cr
= 1-{t\over 2}by lemma 3.2,\cr}}$$
so we have proved:
\theorem{6.6}{If $P$ and $Q$ are two intersecting convex polygons, then their number of edge intersections equals the number of their common tangents.}
\section{7. Monostrofic tracings and applications}
In this section we consider a class of tracings, the {\it monostrofic tracings}\foot\ddag{The word ``monostrofic'' is formed from two Greek roots that mean ``single-turn''. }, that generalize convex tracings. As we will see, these tracings have many special properties and can be used to advantage in deriving new algorithms in computational geometry. We will use them in this section as a tool for developing algorithms for testing whether convex polygons fit into other convex polygons. More formally, we have the following definition.
\definition{7.1}{A tracing is called {\it monostrofic} if it is a tour in which the car faces in each direction exactly once.}
Obviously all convex tracings are monostrofic.
\lemma{7.1}{The convolution of two monostrofic tracings is monostrofic.}
This lemma provides us with a family of examples of non-convex monostrofic tracings: the convolutions of two oppositely oriented convex tracings, such as the convolution of the oppositely oriented square and diamond shown in figure 5.3. These tracings arise, for instance, in computing the outer common tangents of two convex polygons via the convolution construction. Recall from the last section that the inner common tangents of two similarly oriented convex tracings $P$ and $Q$ correspond to the tangents from the origin to $P\ast Q↑\N$, which is also a convex tracing. The outer common tangents, however, correspond to the tangents from the origin to $P\ast (\op Q)↑\N$, which is monostrofic but non-convex. This situation is somewhat puzzling at first. Could it be that outer common tangents are more difficult to compute than inner common tangents?
Intuitively we expect the answer to be no. And this turns out to be so because the algorithms that find the tangents from a point to a convex tracing also work for computing the tangents from a point to a monostrofic tracing! We do not have the space to develop this observation further here, but this fact is indicative of the many properties of convexity that monostrofic tracings share. In a monostrofic tracing the car is always turning left or always turning right. If we assume, without loss of generality, that the car is always turning left then the lemma below summarizes a number of properties of monostrofic tracings that will be important in the application we want to explore below. An example of a monostrofic tracing illustrating the theorem is shown in figure 7.1.
\lemma{7.2}{Left-turning monostrofic tracings
\item are closed under convolution
\item have degree equal to 1
\item have no regions of winding number greater than 1
\item have at most one region of winding number equal to 1.
\tp Such a region is convex, bounded, and either to the left (in the orientation sense) of all sides, or to the right of all sides.}
We now proceed to study the issue of finding placements of one or more convex polygons in another. By placements we mean translations that cause the enclosed polygon to be fully contained in the enclosing polygon. Notice that we do not allow rotations of the given polygonal shapes.
Suppose that a monostrofic tracing of the form $P\ast (\op Q)↑\N$ has a region of winding number 1. What does that region represent? For each point $z$ we have $\dg(P\cdot (\op Q)↑{\tran z}) = \wi(z,P\ast (\op Q)↑\N)$, so wherever the latter expression equals 1, then so does the former. The fact that $\wi(z,P\ast (\op Q)↑\N) = 1$ is equivalent to $\wi(O,P\ast (\op Q)↑{\tran z\,\N}) = 1$, i.e., that $P$ and $(\op Q)↑{\tran z}$ intersect. But recall, from lemma 4.6, that for oppositely oriented convex tracings $P$ and $\op Q$ the degree $\dg(P\cdot (\op Q)↑{\tran z})$ is one minus half the number of edge intersections. The latter number in this case must be zero. Therefore we have proved:
\theorem{7.3}{A point $z$ has winding number 1 with respect to $P\ast (\op Q)↑\N$ if and only if either $P$ is entirely contained in $Q↑{\tran z}$, or $Q↑{\tran z}$ is contained entirely in $P$.}
We can make a counterclockwise traversed convex tracing out of the region of winding number 1, to be denoted by $P\vdash Q$. Some useful properties of $P\vdash Q$ are given in the two lemmata below.
\lemma{7.4}{The tracing $P\vdash Q$ can be computed in linear time.}
We can distinguish whether it is $P$ that can fit in $Q$ or vice-versa as follows:
\lemma{7.5}{If $Q$ fits in $P$ then all sides of $P\vdash Q$ are portions of sides of $P$ (in the convolution); if $P$ fits in $Q$ then they are all portions of sides of $Q$; and if neither statement is true, then $P\vdash Q$ is a single full turn.}
Now let us consider the simultaneous and disjoint placement of two convex polygons $P$ and $Q$ into a third $R$, as in figure 7.2. Let $u$ and $v$ respectively denote valid placements of $P$ and $Q$. Then $u$ must be in $P\vdash R$, $v$ in $Q\vdash R$, and by disjointness we must have
$$P↑{\tran u}\inte Q↑{\tran v} = \emptyset \hbox{\rm \ or, equivalently\ } v-u\not\in P\ast Q↑\N.$$
Thus $v-u \in (Q\vdash R)\ast(P\vdash R)↑\N\rslash P\ast Q↑\N$, where ``$\rslash$'' denotes set-theoretic difference. The following lemma states that the converse is also true.
\lemma{7.6}{There exist disjoint placements of two convex polygons $P$ and $Q$ into a third $R$ if and only if
$$(Q\vdash R)\ast(P\vdash R)↑\N\rslash P\ast Q↑\N \emptyset.$$}
This leads to the following rather surprising conclusion:
\theorem{7.7}{It is possible to decide if two convex polygons can be made to disjointly fit into a third, but with no rotations allowed, in linear time.}
Unfortunately this technique does not extend to more than two polygons.
\section{8. Duality}
A natural duality between points and lines in the Cartesian plane has long been known to geometers [\Cox]. Under this duality a point with coordinates $(a, b)$ corresponds to the line with equation $ax+by+1=0$. The point and the corresponding line are called {\it dual} of each other. Geometrically, if $d$ is the distance from the origin $O$ to point $p$, the dual $p\star$ of $p$ is the line perpendicular to $Op$ at distance $1/d$ of $O$ and placed on the other side of $O$ (see figure 8.1). In order to handle all cases, this definition requires that the plane be extended (by the addition of points at infinity) in such a way that it becomes topologically equivalent to a non-orientable surface, the so-called {\it projective plane}. As a consequence of this non-orientability, there is no consistent way to define the ``left side'' of an oriented line, or to define a ``counterclockwise sense of rotation'' for all points of the plane. In particular, this classical dualization prevents us from giving unique and unambiguous duals for all moves and turns.
We solve this problem by using a different extension of the plane, that is endowed with the topology of a sphere (and therefore is orientable). Informally speaking, this extension consists in distinguishing a point on the ``top'' side of the plane from its {\it antipode}, a point with same position but on the ``bottom'' side of the plane. For such a point, the meaning of ``counterclockwise'' is defined with respect to an observer standing on the same side of the plane. So, if a car describes a counterclockwise loop on the top side of the plane, a second car on the bottom side that passes through the same positions in the same order will describe a clockwise loop. We call this extension the {\it two-sided plane} (2SP). One can view this construction algebraically by using homogeneous coordinates, in which a triplet $\hop{x,y\hom w}$ of reals numbers is used to represent the point with Cartesian coordinates $(x/w, y/w)$. In classical homogeneous coordinates we identify the points $\hop{x,y\hom w}$ and $\hop{\lambda x, \lambda y\hom \lambda w}$ for each real $\lambda0$. In the new manifold we only do so if $\lambda>0$. If $\lambda$ is negative, the point $\hop{\lambda x, \lambda y\hom \lambda w}$ is the antipode of the point $\hop{x,y\hom w}$.
A straight line extends to both sides of the 2SP, and therefore it passes through a point if and only if it passes through its antipode. An oriented line has the same direction vector on both sides; however, since the notions of ``left'' and ``right'' are relative to a local observer, a point is to the left of an oriented line $\lscr$ if and only if its antipode is to the right of $\lscr$. The left and right ``half-planes'' of $\lscr$ are well-defined concepts, and their union is the whole 2SP minus the line $\lscr$.
By working on the 2SP, we can define the duality between points and lines so as to preserve relative orientations. Under this mapping, a point $p$ is transformed to an {\it oriented} line $p\star$, and vice versa: the line $p↑\ast$ is oriented counterclockwise (as seen from the origin $O$) if and only if $p$ lies on the top side of the plane\foot\dag{The dual of a line passing through the origin is a {\it point at infinity}, and the dual of the origin is the {\it line at infinity}.}. It follows from this construction that a point $p$ lies to the left of an oriented line $\lscr$ if and only if the dual point $\lscr\star$ lies to the left of the line $p\star$.
This duality extends nicely to states, moves, and turns. The dual of a state is a state, the dual of a move is a turn, and the dual of a turn is a move. A move is forward if and only if its dual turn is counterclockwise. The point where the dual turn occurs is the dual of the tangent to the move; it will be on the top side of the plane if and only if the move is oriented counterclockwise as seen from the origin. If we take the dual of every move and turn of a tracing, the result will be another tracing, the {\it dual} of the first.
The concept of duality is another powerful tool for the study of tracings and for the description, analysis, and construction of algorithms dealing with them. By applying it to theorems, proofs, operations, and algorithms we can obtain twice as many results with practically the same effort. For example, an algorithm for computing the convex hull of $n$ points in the plane {\it automatically} becomes an algorithm for computing the intersection of $n$ half-planes. One fact that makes this technique even more valuable is that certain problems are much easier to visualize in one of the two domains than in the other.
Many of the concepts, operations, theorems, and algorithms given above have important dual versions. For example, winding numbers are the duals of degrees: $\wi(p, A)=\dg(p↑\ast, A\star)$. The dual of the sweep number is the {\it crossing number} $\kr(\lscr, A)=\sw(\lscr\star, A\star)$, which is a signed count of how many times the tracing $A$ crosses the line $\lscr$. The {\it dual product} of two tracings $A$ and $B$, mentioned in section 4.6, is defined as $A\dpr B=(A\star\cdot B\star)\star$. While computing $A\cdot B$ we insert new turns where two moves pass through the same point; in $A\dpr B$ we add new moves connecting vertices of $A$ and $B$ wherever two turns pass through the same oriented line. Thus we see the duality between the operations of intersection and convex hull.
The geometric dual of a convex polygon which encloses the origin can be defined in the classical projective plane, and has in fact been used by several authors. However, we believe that the 2SP and the concept of tracing as we defined here are the simplest formalism that allows that concept to be extended to arbitrary polygons. It is instructive to consider the example of a convex tracing that does not enclose the origin (figure 8.2). Note that the dual tracing contains points on both sides of the plane, since the original contains both counterclockwise- and clockwise-oriented moves; in particular, the vertex $1\star$ is on top, and $2\star$ is on the bottom. The move $1\star2\star$ follows the shortest possible route, namely the straight line segment connecting those two points, which turns out to be the two rays (one on top and one on the bottom) shown in the figure. If the distinction between top and bottom is ignored, there does not seem to be any simple way of interpreting the dual figure as a convex polygon. As a tracing on the 2SP, however, the dual is a perfectly valid convex polygon. Its interior $R$ consists of the hatched region on the top side of the plane, plus the dotted region on the bottom. For any two points $u,v$ in $R$, the segment $uv$ (with the convention mentioned above) lies entirely in $R$.
\section{9. Conclusions}
We have exhibited a new framework for geometric computing based on a set of topological concepts such as direction, tracing, winding number, degree, and sweep number. By the use of fiber products we have a generic way of defining operations on tracings. Our operations generalize classical ones, such as intersection or convex hull, and include powerful new ones, such as convolution. Finally, the precise duality we have introduced helps to elucidate several connections between these concepts.
We believe this new framework offers an important new set of tools for developing, understanding, and verifying geometric algorithms.
\section {10. References}
\ref [\CD] {\refauth{Chazelle, B., and Dobkin, D.}
\reftit{Detection is easier than computation.}
\refpub{Proc. 12th Annual ACM Symp. on Theory of Computing (Apr. 1980), 146--152}}
\ref [\Cox] {\refauth{Coxeter}
\reftit{{\bf Introduction to Geometry}.}
\refpub{John Wiley & Sons, 1969}}
\ref [\EMP] {\refauth{Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D.}
\reftit{Stabbing line segments.}
\refpub{BIT Vol. 22 (1982), 274--281}}
\ref [\Fi] {\refauth{Fischer, M. J.}
\reftit{The mountaineer's problem.}
\refpub{Problem 82-1, J. of Alg., vol. 3 (1982), 177--178}}
\ref [\GP] {\refauth{Guillemin, V., and Pollack, A.}
\reftit{{\bf Differential Topology}.}
\refpub{Prentice Hall, 1974}}
\ref [\GrY] {\refauth{Graham, R. L., and Yao, F. F.}
\reftit{Finding the convex hull of a simple polygon.}
\refpub{J. of Algorithms (to appear)}}
\ref [\IK] {\refauth{Iyanaga, S., and Kawada, Y.}
\reftit{{\bf Encyclopedic Dictionary of Mathematics} {\rm (2nd. ed.)}.}
\refpub{MIT Press, Cambridge, Mass., 1968}}
\ref [\Kn] {\refauth{Knuth, D. E.}
\reftit{{\bf TEX and Metafont}.}
\refpub{Digital Press, 1979}}
\ref [\La] {\refauth{Lang, S.}
\reftit{{\bf Differential Manifolds}.}
\refpub{Addison-Wesley, 1972}}
\ref [\OvL] {\refauth{Overmars, M. H., and Leeuwen, J. van}
\reftit{Maintenance of configurations in the plane.}
\refpub{Journal of Computer and System Sciences [Issue unknown] (1981), 166--204}}
\ref [\Ni] {\refauth{Nievergelt, J.}
\reftit{Sweep-line algorithms in computational geometry.}
\refpub{Personal communication}}
\ref [\PM] {\refauth{Preparata, F. P., and Muller, D. E.}
\reftit{Finding the intersection of $n$ half-spaces in time $O(n\log n)$.}
\refpub{Theor. Comp. Sc. Vol. 8 (1979), 44-55}}
\ref [\Sch] {\refauth{Schwartz, J. T.}
\reftit{Finding the minimum distance between two convex polygons.}
\refpub{Information Processing Letters Vol. 13, 168--170 (1981)}}
\ref [\Sh] {\refauth{Shamos, M. I.}
\reftit{Computational geometry {\rm (Ph. D. thesis)}.}
\refpub{Yale Univ. (Dec. 1977)}}
\ref [\TLP] {\refauth{Lozano-Perez, T.}
\reftit{Spatial planning: A configuration space approach.}
\refpub{IEEE Trans. on Comp. To appear Feb. 1983}}
\ref [\Tou] {\refauth{Toussaint, G. T.}
\reftit{Solving geometric problems with the ``rotating caliper''.}
\refpub{Proceedings of Melecon '83, Athens, Greece}}
\par\vskip 20pt
\hrule
\vfill\eject\end