\begfile{KinFOCS2.tex of September 12, 1983 1:00 pm --- Stolfi}


\section{4. Operations on tracings}

We now proceed to develop a calculus of operations on tracings, including addition, convolution, and multiplication. In the current write-up we will place emphasis on conveying the intuitive semantics of these operations and conduct most of the discussion in informal terms. We will also rigorously define each operation by algebraic formulas that give the multiplicity of a state in the resulting tracing. However, due to lack of space, discussion of those formulas and a proof of their validity is relegated to a later publication. In general, this proof consists of showing that the resulting multiset of states is a partial tracing, and is integral and balanced whenever the operands are.

\subsection{4.1 Addition and time reversal}

The addition of two (partial) tracings $A$ and $B$ is simply their multiset sum, denoted by $A+B$: the multiplicity of a state in $A+B$ is the algebraic sum of its multiplicities in $A$ and in $B$. The {\it time reversal} of a tracing $A$ consists of the car going through the same sequence of states in the reverse order; clearly, this corresponds to inverting the sign of the multiplicity of every state in $A$, so we denote the resulting tracing by $-A$. Obviously $A+(-A)$ is the null tracing. In general, for any integer $k$ we denote by $kA$ the tracing which is the sum of $k$ copies of $A$. 

\subsection{4.2. Affine maps and orientation reversals}

Let $M$ be an affine map [\Cox] of the plane into itself; we denote by $P^M$ the image of a point (or set of points) $P$ under $M$. In section 2 we have already seen two examples of affine maps, namely translation by a vector $v$ ($P^{\tran v}$) and $180\deg$ rotation around the origin ($P^N$). An one-to-one affine map $M$ takes a straight line to another straight line. We define the image of a state $s$ under $M$ as the state $s^M$ with position ${\po s}^M$ and tangent line ${\ta s}^M$. Note that an affine map of negative determinant reverses the orientation of the car. This definition extends naturally to moves, turns, trips, and tracings. Compositions of affine maps are affine. If $M$ and $M\pr$ denote two such maps, then the result of applying first $M$ and then $M\pr$ to tracing $P$ will be denoted by $P^{MM\pr}$. This agrees with our use in section 2 of $A^{N\,\tran x}$ to denote the figure $A$ rotated by $180\deg$ and then translated by the vector $x$.

\subsection{4.3. Convolution}

We are now ready to define the {\it convolution} $A\ast B$ of two tracings $A$ and $B$, which will turn out to be a natural extension of the point set operation defined under that name in section 2. We will define $A\ast B$ by means of a construction procedure that essentially follows the basic rule, the {\it fiber product}, discussed there: we take all pairs $a, b$ of parallel states, one from $A$ and one from $B$, and for every such pair we put in the convolution a ``sum'' state $a+b$, whose orientation is the common orientation of $a$ and $b$ and whose position is the vector sum of $\po a$ and $\po b$.

The multiplicities of the states are taken into account in the pairing process. Thus, if $a$ occurs $k$ times in $A$ and $b$ occurs $\lscr$ times in $B$, then we must consider the pair $a,b$ as occurring a total of $k\lscr$ times, each contributing one copy of the sum state $a+b$ to the tracing $A\ast B$.

{\small

If $A$ and $B$ have parallel moves, there would be infinitely many pairs of states, one of $A$ and one of $B$, all adding to the same state of the convolution. We avoid this problem by ignoring such pairs, that is, considering only pairs where at least one of the states belongs to a turn. The formulas below embody this convention and give a rigorous definition of convolution:
$$\eqalign{\mu\xpm
{A\ast B}(s)
    =\sum
{{\scriptstyle\scrp {\po x+\po y=\po s}}
           \atop{\scriptstyle {\di x=\di y =\di s}}}
         \mu\xpm
A(x)\tau
B(y)+\mu\xpm
B(x)\tau
A(y)\cr\vc
\tau\xpm
{A\ast B}(s)
    =\sum
{{\scriptstyle\scrp {\po x+\po y=\po s}}
           \atop{\scriptstyle\di x=\di y =\di s}}
         \tau\xpm
A(x)\tau\xpm
B(y)\cr}$$

}

The above imply that convolution is a {\it bilinear operation}: For any tracings $A$, $B$, and $C$, we have $A\ast (B+C)=(A\ast B)+(A\ast C)$, and similarly on the other side. This property is the key both to a better understanding of what convolution means, and to an effective algorithm for computing it. Recall that every tracing can be written as the sum of individual moves or turns. By bilinearity, the convolution $A\ast B$ will be the sum of all the convolutions $A
i\ast B
j$ of a move or turn of $A$ with one of $B$. According to the formulas, we have only to consider the cases of ``turn $\ast$ turn'', ``turn $\ast$ move'', and ``move $\ast$ turn''; the convolution of two moves is always the null tracing. 

The convolution of two left turns $t
1, t
2$ with positions $p
1$ and $p
2$ is a left turn at position $p
1+p
2$. The set of directions swept by each $t
i$ can be viewed as an arc $\alpha
i$ on the unit circle. The states in the convolution $t
1\ast t
2$ then will be exactly those with directions in $\alpha
1\inte\alpha
2$\foot\dag{If one of the turns is greater than $180\deg$, the intersection $\alpha
1\inte\alpha
2$ may consist of two disjoint arcs. In that case the convolution $t
1\ast t
2$ will consist of two left turns.}. See figure 4.1.

Let us consider now the case of a left turn $t$ convolved with a forward move $m=\la r\sp s\ra$, or vice-versa. We have two subcases: if the orientation of $m$ does not belong to the arc of directions swept by $t$, there are no matching pairs of states, and the convolution $t\ast m$ null. Otherwise, there will be a single state $x$ of $t$ that is parallel to $m$. The convolution $t\ast m$ is the forward move obtained by adding $x$ to every state of $m$, that is, the move $\la r+x\sp s+x\ra$; see figure 4.1. Clearly, these two rules are consistent with the basic rule of adding parallel states of the two operands.

The bilinearity property determines the result of convolutions involving backward moves and/or right turns (that is, elements with negative multiplicities). For example, the convolution of a forward move and a right turn is a backward move, and the convolution of two right turns is a left turn. An example of the convolution of two tracings is shown in figure 4.2. For the statements of the theorems below recall that the term tracing is used to denote an integral and balanced partial tracing.

\theorem{4.1}{The convolution of two tracings is a tracing.}

From the discussion above it is clear that the convolution of tracings is both associative and commutative. Furthermore, if $M$ is a {\em linear} map, then $(A\ast B)^M = A^M\ast B^M$. If $v$, $w$ are two vectors, then $A^{\tran v}\ast B^{\tran w} = A^{\tran w}\ast B^{\tran v}=(A\ast B)^{\tran{{v+w}}}$. Therefore, translations of the operands do not affect the shape of the convolution. As a final comment, we note that:

\theorem{4.2}{If $A, B$ are of size $O(n)$, then $A\ast B$ is of size $O(n^2)$.}

This bound is tight, as the example of figure 4.3 shows. This is in contrast with the convex case, to be discussed below. Algorithms for computing general polygonal convolutions are an interesting topic, but will not be discussed further in this paper.

\subsection {4.4. Convolution and convexity}

The convolution of convex tracings is fundamentally simpler than the general case. Figure 4.4 illustrates the simple case of convolving a square with a diamond. 

\theorem{4.3}{The convolution of two similarly oriented convex tracings is a similarly oriented convex tracing, obtained by merging the edges of the two factors in slope order.}

As a consequence of this theorem, the convolution of two similarly oriented convex tracings can be computed {\it in linear time}. Note that reversing the sense of traversal on one of the factors reverses the sense of traversal in the convolution, but does not otherwise change the set of result states. Reversing the orientation of one of the factors, however, can have profound effects, as we will see in sections 6 and 7.

\subsection{4.5. Product}

It is easy to check that the winding number function $\wi$ is {\it linear} with respect to the second argument; that is, for any point $p$ and any tracings $A, B$, we have $\wi(p, A+B)=\wi(p, A)+\wi(p, B)$. This property is so important that it can almost be regarded as the ``definition'' of the tracing $A+B$. From this point of view, it is natural to ask whether we can define the {\it product} $A\cdot B$ of two tracings $A$ and $B$, with the property that $\wi(p, A\cdot B)=\wi(p, A)\wi(p, B)$. Surprisingly, the answer is ``yes''.

The process of computing the product is informally as follows. We break every move of $A$ into submoves at every point where it crosses the path of $B$. Analogously, we break every move of $B$ at the points where it crosses $A$. After this is done, all points of a particular (sub)move $m$ of $A$ have the same winding number with respect to $B$, denoted by $\wi(m, B)$; similarly, all points of a given move $n$ of $B$ have the same winding number $\wi(n, A)$ with respect to $A$. The product tracing is constructed then by taking $\wi(m, B)$ copies of every move $m$ of $A$, and $\wi(n, A)$ copies of every move $n$ of $B$. Every turn of $A$ and $B$ is handled in the same way, according to the winding number of its vertex with respect to the other tracing. See figure 4.5. Note that every move or turn that is copied into the product retains its original orientation.

At a point where the two tracings cross, the above rules will result in unbalanced states, some with an excess of incoming moves and some with an excess of outgoing ones. Fortunately the balance can be restored at those points by adding extra turns. By convention, every such turn is less than $180\deg$, and connects an incoming move derived from one tracing to an outgoing move derived from the other. This turn will bound the regions of highest winding number for the two tracings at that vertex.

{\small

For the exact definition of product, we need first introduce the ``displaced winding numbers'' $\wi\xp(s)$ and $\wi\xm(s)$, that give the values of $\wi(p)$ for a point $p$ respectively just ahead and just behind the state $s$. These are given by the formulas
$$\wi\xp(s)=\sum
{r\in (s\sp \infty)}\,\,\,
  \sum
{t\in\laa r\sp \op r\raa} \mu(t)$$
and
$$\wi\xm(s)=\sum
{r\in [s\sp \infty)}\,\,\,
  \sum
{t\in\laa r\sp \op r\raa} \mu(t).$$

The state counting functions for the product are then defined by
$$\eqalign{
\mu\xpm
{A\cdot B}(s)=\mu\xpm
A(s)w\xpm
B(s) + \mu\xpm
B(s)w\xpm
A(s)\cr\vc
\tau\xpm
{A\cdot B}(s)=\tau\xpm
A(s)w
B(s)+\tau\xpm
B(s)w
A(s)
    -\tau\xpm
A(s)\tau\xpm
B(s)\cr\va
\null\hskip10pt +\sum
{x\in (\op s\sp s\ra}\,\,\,
    \sum
{y\in \la s \sp \op x)}
      \biglp \Pi
{A,B}(x,y)+\Pi
{B,A}(x,y)\bigrp\cr\vc
\null\hskip10pt \pm{1\over2}\sum
{x\in \laa s\sp\op s\raa}
      \biglp \Pi
{A,B}(x,s)+\Pi
{B,A}(x,s)\bigrp\cr\vc
\null\hskip10pt -{1\over2}\;\; \Pi
{A,B}(s,s)\cr
}$$
where
$$\Pi
{A,B}(x,y)={{\mu\xp
A(x)\mu\xm
B(y)+\mu\xm
A(x)\mu\xp
B(y)}\over 2}.$$

These formulas apply to any partial tracings $A$ and $B$. However, the product of two integral balanced tracings $A$ and $B$ is a tracing only if $A$ and $B$ have no oppositely oriented moves or turns with coincident positions.

} % end of \small

\theorem{4.4}{The product of two tracings $A$ and $B$ containing no two states, one from $A$ and one from $B$, with the same position and opposite orientations, is a tracing.}

{\small

If this condition is violated, the product will be balanced but may contain moves and turns with half-integer multiplicities. In any case, the winding numbers in the product tracing have the following property:

$$\eqalign{\wi
{A\cdot B}(s)=\wi
A(s)\,\wi
B(s)\cr\vb
    \null\hskip10pt +{1\over4}\bigglp \sum
{\scrp {\po z=\po s}}\;\mu
A(z)\biggrp
        \bigglp \sum
{\scrp {\po z=\po s}}\;\mu
B(z)\biggrp\cr\vb
    \null\hskip10pt -{1\over4}\sum
{\scrp {\po z=\po s}}\;\;
        \biglp \mu\xp
A(z)\,\mu\xm
B(\op z)
          +\mu\xm
A(z)\,\mu\xp
B(\op z)\bigrp\cr}.$$

In particular, if neither $A$ nor $B$ pass through the point $\po s$, this equation reduces to $\wi
{A\cdot B}(s)=\wi
A(s)\wi
B(s)$.
 
} % end of \small

There is another way of looking at the product definition that is quite similar to the basic state-pairing principle used in constructing the convolution. We consider all pairs of states $x, y$ such that $\po y$ is on the ray out of $x$. For every such pair where $x$ occurs in one tracing, and the other tracing {\em moves} through $y$, we add to the product $A\cdot B$ a multiple of the state $x$, depending on the orientation of $y$. Specifically, we use a coefficient of $+1$ if $\di y$ lies to the left of $\di  x$, $0$ if $\di  y = \di x$, and $-1$ if $\di y$ lies to the right. We also consider all pairs $x, y$ where $\po x=\po y$ and $y\in(x\sp \op x)$; for every such pair where one tracing moves through $x$ and the other moves through $y$, we add to the product one copy of the turn $\la x\sp y\ra$. See figure 4.6. As in the convolution, if $x$ occurs $k$ times in one tracing, and the other moves through $y$ $\lscr$ times, we must consider the pair $x, y$ as occurring $k\lscr$ times, and add its contribution that many times to the product tracing. 

To see why these rules are equivalent to the ones given above, recall the definition of winding numbers. Clearly, the first rule will add to the product a given state $s$, which occurs $\alpha$ times in $A$ and $\beta$ times in $B$, a total of $\alpha\cdot \wi
B(\po s)+\beta\cdot \wi
A(\po s)$ times. The second rule provides the additional turns needed to balance the product tracing.

From this discussion (and, rigorously, from the algebraic formulas) we can see that product is a bilinear operation, as well as being commutative and associative. Affine maps distribute over product: for any map $M$, $(A\cdot B)^M=A^M\cdot B^M$.

The addition and multiplication of tracings can be seen as a generalization of the union and intersection of figures. Let us define the {\it interior} of a tracing $A$ as the set of points of nonzero winding number with respect to $A$. Now consider the class of tracings whose winding number functions assume no negative values. This class is closed under addition and product; the interior of $A+B$ is the union of the interiors of $A$ and $B$, while the interior of $A\cdot B$ is the intersection of these interiors. As with the convolution, the product of convex tracings is particularly simple.

\theorem{4.5}{If $P$ and $Q$ are similarly oriented convex tracings, then $P\cdot Q$ is a similarly oriented convex tracing corresponding to their classical intersection.}

Even for oppositely oriented convex tracings multiplication has nice properties. The following result, illustrated in figure 4.7, will be useful later on:

\lemma{4.6}{If $P$ and $Q$ are counterclockwise traversed but oppositely oriented intersecting convex tracings and $i$ is the number of their edge intersections, then $\dg(P\cdot Q) = 1-i/2$.}

{\small

\subsection{4.6. Other operations}

Both the convolution and the product operations can be defined within a generic framework of matching states of two tracings according to a certain criterion, with each matched pair contributing a result state (or states) depending on the pair. A pairing of this sort is called a {\it fiber product}. Many other interesting operations on tracings can be defined this way. For example, one can define the {\it dual product} $A\dpr B$ of two tracings $A$ and $B$, which has the property that $\dg(\lscr, A\dpr B)=\dg(\lscr, A)\dg(\lscr, B)$ for every line $\lscr$ that is not a common tangent of $A$ and $B$. This operation generalizes the notion of convex hull, in the same way that $A\cdot B$ generalizes the notion of intersection of figures. A fiber product pairing states where the car on $A$ faces the car on $B$ is useful in developing algorithms for computing the intersection of convex polygons and the convex hull of a simple polygon. Due to lack of space we cannot discuss these developments here.

}

\section{5. The fundamental theorem of convolutions}

In this section we will show how the winding numbers $\wi(x, A\ast B)$ of the convolution are related to the tracings $A$ and $B$, in a manner that is easily interpreted as a generalization of convolution discussion presented in section 2. It is not enough for us to know whether $x$ is ``inside'' $A\ast B$ or not; we would like to know also ``how much inside'' it is, i.e., what is the value of $\wi(x, A\ast B)$. In order to do this, we will have to replace the yes-no test ``$A\inte B^{N\,\tran x}\neq\empty$'' of equation (5) of section 2 by one giving a numeric result. To gain some intuition about what this test should be, let's consider the example of figure 5.1, in which $B$ is a diamond of diagonal $r$, and $A$ is a pair of squares of size $R$, placed less than $r$ away from each other. All tracings are oriented and traversed counterclockwise.

The convolution of the two tracings will be a pair of octagons, as shown in the figure; the numbers there show the values of $\wi(p, A\ast B)$ in each ``region'' of the tracing. Now let us see how those numbers could arise from the characterization suggested by equation (5) of section 2. We see that a point $p$ with $\wi(x, A\ast B)=k$ ($k=0, 1$ or $2$) is one for which $A\inte B^{N\,\tran x}$ has exactly $k$ components. This result is on the right track: with only a little more elaboration, it will give us a precise expression for $\wi(x, A\ast B)$. We need only replace ``intersection'' and ``number of components'' by suitable concepts that are applicable to general tracings.

It turns out that we already have the necessary concepts: the multiplication of two tracings is the right replacement for ``intersection'', and the proper way to count the ``components'' of the result is by taking its degree, as defined in section 3.5.

\theorem{5.1.\ {\rm (The convolution theorem)}}{If $A$ and $B$ are two polygonal tracings, then $\wi(x,A\ast B) = \dg(A\cdot B^{N\,\tran x})$ everywhere.}\par

Note that when the convolution $A\ast B$ passes through $x$, the tracings $A$ and $B^{N\,\tran x}$ will generally contain pairs of opposite states, and their product $A\cdot B^{N\,\tran x}$ may be non-integral. This is to be expected, since in such cases the winding number $\wi(x,A\ast B)$ may be fractional, and no integral, balanced tracing can have fractional degree.

We now look at some illustrations of this theorem. Consider the convolution of a square $A$ with a diamond $B$, both oriented and traversed counterclockwise, as in figure 5.2. For a point $x$ inside the convolution ($\wi=1$) the product of the square by the inverted diamond placed at $p$ is a counterclockwise oriented and traversed convex polygon, whose degree is $1$. If $x$ is outside the convolution, the inverted diamond at $x$ does not meet the square, so the product is empty. This gives $\wi=\dg=0$. And if $x$ is on the convolution, then both sides yield $1 \over 2$.

Now consider the example of figure 5.3, where the same diamond $B$ is convolved with a square $A$ oriented and traversed in the opposite sense. For a point $x$ in the region of winding number $-1$, the product $A\cdot B^{N\,\tran x}$ is simply $B$ traversed clockwise, which has $\dg=-1$. The case of points, such as $y$, inside the square but outside $A\ast B$ is more interesting. At first glance it may appear that here too the product has degree $-1$. However, a careful examination of all the turns made by the car in the product tracing shows that their sum is indeed $0$. For $z$, in the region with $\wi=1$, the turns of the product add to one complete counterclockwise revolution, so $\dg=1$. 

Figure 5.4 shows the two squares of the preceding two examples, which are traversed and oriented in opposite directions, combined into one tracing and convolved with the same diamond. Notice that the region of non-negative winding number is exactly the area of the plane that would be painted black if a diamond-shaped brush were swept along the square. It was precisely for this application that the kinetic framework was originally developed.

\input KinFOCS3.tex