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

\def\Figi{F1}
\def\Figii{F2}
\def\Figiii{F3}
\def\Figv{F5}
\def\Figvii{F7}
\def\Figviii{F8}
\def\Theii{2}
\def\Theiii{3}
\def\Theiv{4}
\def\Thev{5}
\def\Thevi{6}
\def\Thevii{6}
\def\Theviii{8}
\def\Theix{9}
\def\Thex{10}
\def\Thexi{11}
\def\Thexii{12}

Besides convolution, we will need in the future a few other fundamental operations acting on polygonal tracings. The geometric transformations of the plane (like translations, rotations, scalings and so forth) extend to tracings in a most natural way. Addition and multiplication, that we define further on, are more specific to tracings, and will prove essential for understanding the meaning of convolution.

Intuitively speaking, we can define a {\it geometric transformation} as a mapping from one space into another that takes geometric objects into other geometric objects. Such transformations have been studied quite extensively by generations of mathematicians, and F. Klein’s school regarded them as the true foundation of geometry. Isometries of the plane (rotations, reflections and translations) were taken for granted by Euclid himself, and the concepts of scaling and shearing transformations were clearly familiar to him.

For lack of time and space, a satisfactory introduction to geometric transformations will be left to some future chapter; for now, we will restrict ourselves to the definitions and notation strictly necessary for the rest of this chapter.

The simplest transformation is the identity $I$, that maps every point into itself. A {\it translation} by a vector $v$, of course, is the map that takes every point $x$ of the plane to the point $x+v$. A translation is a special case of an {\it isometric transformation}, or {\it congruence}, a geometric map that preserves the distances between all pairs of points. Rotations and reflections around a line are also isometric transformations. It is easy to see that isometries must map straight lines into straight lines, and preserve the angles between them. Indeed, in classical geometry two figures related by a congruence are usually considered to be the same figure.

A slightly more general kind of geometrical mapping is a {\it similarity transformation} that is basically an isometry followed by a change of scale. A similarity will map straight lines into straight lines, angles into equal angles, and in general figures into similar figures (hence its name). Generalizing in a different way, we get a class of transformations that preserve straight lines and areas but not necessarily angles and distances; we may call them {\it unimodular transformations}. The ``vertical shearing’’ that maps a point $(x, y)$ to the point $(x, y+\alpha x)$ (for some nonzero constant $\alpha$) is an element of this class.

The {\it affine transformations} constitute a more general class of mappings, including all of the above as proper subclasses. General affine maps take straight lines into straight lines, but do not in general preserve angles, distances or areas (they preserve {\it ratios} of areas, however). The affine maps that leave the origin fixed are the well-known {\it linear transformations} of $\Reals↑2$. A general affine transformation consists of a linear map followed by a translation.

An affine transformation $T$ is {\it degenerate} if it is not one-to-one; this happens if and only if two distinct points have the same image under $T$. Given a pair of non-degenerate triangles $abc$ and $a\pr b\pr c\pr$, there is exactly one (non-degenerate) affine transformation that maps $a$ to $a\pr$, $b$ to $b\pr$, and $c$ to $c\pr$.\fig3
Conversely, any non-degenerate affine map of the plane will take the points $(0, 0)$, $(0, 1)$ and $(1, 0)$ to the vertices of a non-degenerate triangle. In this chapter, all affine maps will be assumed one-to-one unless stated otherwise.

We will denote by $p↑T$ the image of a point $p$ by the affine transformation $T$. If $X$ is a set of points, $X↑T$ is the set $\rset{p↑T\relv p\in X}$. The image of a line $\lscr$ is written $\lscr↑T$; its orientation is such that a point $p$ is on $\lscr$ (resp. to the left of $\lscr$) if and only if $p↑T$ is on $\lscr↑T$ (resp. to the left of $\lscr↑T$).\fig4

Note that if $\lscr$ is oriented from $a$ towards $b$, then depending on the map $T$ the image $\lscr↑T$ may be oriented from from $a↑T$ to $b↑T$ or from $b↑T$ to $a↑T$. It can be shown that if this ``orientation reversal’’ happens for one line, it happens for all of them. The mapping $T$ is said to be {\it odd} if that occurs, and {\it even} otherwise. An affine transformation is odd if and only if it maps a counterclockwise triangle into a clockwise one.

The image of a turn of move $[r\to s]$ under an affine map $T$ will be precisely the turn or move $[r↑T\to s↑T]$. This is not entirely obvious at first sight; it follows from the fact that affine transformations preserve the ``betweeness’’ properties of points and oriented lines, i.e. they map segments into segments and proper angles into proper angles. More precisely, a point $x$ belongs to the segment $(p\span q)$ if and only if $x↑T$ is in $(p↑T\span q↑T)$. Similarly, if the three lines $r, s$ and $t$ are such that $\stdir t$ is in the proper arc $(\stdir r\span \stdir s)$, then the same relationship holds for their images under $T$.\fig3

The image $S↑T$ of a tracing $S$ under an affine map is then defined quite naturally as the result of applying $T$ to every turn and move of $S$. For example, if $T$ is translation by a vector $v$, then $S↑T$ will be what we would expect.\fig3

Note that if $T$ is an odd affine map, then the move $[r\to s]↑T$ will be backwards if $[r\to s]$ is forward, and vice-versa. In the same way, an odd map will change clockwise turns into counterclockwise ones, and conversely. (If you are beginning to feel confused, don’t worry: all maps we will use in this chapter are even).

We will denote by $-I$ the {\it sign reversal} transformation that maps every point $(x, y)$ to its opposite $(-x, -y)$ across the origin. This transformation corresponds to a $180\deg$ turn around the origin, or to two successive reflections, one about each coordinate axis. In spite of the fact that it maps every line to one with opposite orientation, it is an even mapping (can you see why?). One of its properties is that any tracing which is centrally symmetric (e.g., a circle) is identical to its image under $-I$, up to orientations and directions of traversal.\fig3

The affine maps are closed under composition, and the same is true of the other classes of transformations defined above. In other words, if $R$ and $S$ are arbitrary affine maps, then there is a third affine map $R S$ such that $x↑{R S}=(x↑{S})↑R$ for all $x$ in the plane. We denote the translation through a vector $v$ by just $v$, so $x↑{v\,-I}$ is what we obtain by applying the sign reversal transformation $-I$ to $x$, and then translating the result by $v$\foot\dag{Do not try to read $v\,-I$ as the difference between $v$ and $I$; the similarity of notation is just an unlucky coincidence.}. This particular transformation will play an important role in the next section.

It is interesting to consider the interaction between affine maps and convolution of polygonal tracings. If $T$ is a linear map, then $A↑T\ast B↑T=(A\ast B)↑T$. This is not true for general affine maps, in particular for translations; however, it is the case that $A↑v\ast B↑w=(A\ast B)↑{(v+w)}$, for any vectors $v$ and $w$. Since sign reversal is a linear map, we have $A↑{v\,-I}\ast B↑{w\,-I}=(A\ast B)↑{(v+w)\,-I}$.\fig4

In this section we proceed to define two operations, the {\it sum} $A+B$ and the {\it product} $A\cdot B$ of two polygonal tracings $A$ and $B$. The motivation for them comes from our original interpretation of tracings as the outlines of figures: as we will see, addition and multiplication of the tracings are roughly the equivalents of union and intersection of the corresponding figures. Furthermore, in the next section we will need the concept of product in order to relate the convolution of tracings to our original brush-and-trajectory metaphor.

The reason we call them sum and product is that
$$\eqalign{w(p, A+B)|=w(p, A)+w(p, B) \hbox{\quad and}\cr
w(p, A\cdot B)|=w(p, A)w(p, B),\cr} \eqno(2)$$
whenever $w(p, A)$ and $w(p, B)$ are defined (i.e., whenever the point $p$ is not on any move of $A$ or $B$), and whenever the tracings $A+B$ and $A\cdot B$ are defined.

Addition is easy: we just take a new tracing $A+B$ whose tours are the multiset union of $A$ and $B$. Clearly, the result is always a valid tracing that satisfies equation (2). Indeed, we can consider every tracing as being the sum of all its turns. Addition of tracings is obviously asociative and commutative; furthermore, one can easily check that, for any tracings $A$, $B$ and $C$, we have $A\ast (B+C)=(A\ast B)+(A\ast C)$. Affine transformations distribute over addition: $(A+B)↑T=A↑T+B↑T$ for any $A$, $B$ and $T$.

Multiplication of tracings is a bit more involved. The reader at this point might enjoy trying to construct by himself the product of the two tracings shown below, before reading further.\fig4

If $[u\to v]$ is a move of $A$, we say that the segment $(\stpos u\to\stpos v)$ is one of its {\it edges}, and the critical points $\stpos u, \stpos v$ are two of its {\it vertices}. For brevity, let’s call the points of the plane traversed by a tracing $A$ (both critical and non-critical) the {\it points of $A$}. Most naturally, we will call a point that is in both $A$ and $B$ an {\it intersection point}, or simply {\it intersection}, of the two tracings.

In order to to give a correct definition of the product of two tracings $A$ and $B$, we will need to impose certain restrictions on them. An intersection $x$ of $A$ and $B$ is {\it proper} if there is no pair of states $a$ of $A$ and $b$ of $B$ having position $x$ and opposite orientations. We say that $A$ and $B$ {\it intersect properly} if all their intersections are proper. In terms of the informal analogy, this means the two cars never pass through the same spot facing towards each other. The figure below illustrates the various kinds of intersections.\fig{3.5}

\mfig5
We will define the product $A\cdot B$ only if $A$ and $B$ intersect properly. To make the construction easier to understand, we will describe it first for a simple case. Let’s assume that every intersection of the original tracings belongs to exactly one edge of $A$ and exactly one edge of $B$ with different orientation; in particular, no vertices of either $A$ or $B$ are intersection points, intersecting edges have multiplicity one, and no edges intersect at more than one point.
\endmfig

\mfig6
The first step of the product procedure consists in modifying the two tracings so that any two edges $a$ of $A$ and $b$ of $B$ are disjoint. This situation can always be arrived at by breaking every move of one tracing that passes through an intersection into two consecutive moves connected by a turn of zero degrees. Note that the number of breaks that have to be introduced is finite, and also that the winding number of any point with respect to either tracing is not affected by this operation.
\endmfig

After this operation, the edges of $A$ and $B$ do not cross; therefore, all points of a given edge $a$ of $A$ have the same winding number with respect to $B$, denoted by $w(a, B)$. If $w(a, B)$ is positive, we put in the product tracing that many copies of the move corresponding to $a$. If $w(a, B)$ is negative, we put instead $\leftv w(a, B)\rightv$ copies of its time reversal. Similarly, for each edge $b$ of $B$ we take its corresponding move with multiplicity $w(b, A)$, with the same interpretation if this number is negative.\fig3

Let’s now consider the turns of the product tracing. Let $t$ be an original turn of $A$ (i.e. one that was present before the breakup step) and let $a1̌, a2̌$ be the moves preceding and following it in $A$. Because of our simplifying assumptions, the vertex $v$ of $t$ is not on $B$, and we have $w(a1̌, B)=w(a2̌, B)=w(v, B)$. Then the product tracing will contain that many copies of the turn $t$, each connecting one copy of $a1̌$ to one copy of $a2̌$. As in the case of moves, if $w(v, B)$ is negative we take $\leftv w(v, B)\rightv$ copies of the time reversal of $t$. The same rule applies with $A$ and $B$ interchanged.\fig3

At the other vertices (i.e., at the intersections of the original tracings), the situation is more interesting. According to our assumptions, there will be two edges $a1̌$ of $A$ and $b1̌$ of $B$ coming into any such vertex $x$, and also two edges $a2̌$ of $A$ and $b2̌$ of $B$ coming out of it. Moreover, the edges $a1̌$ and $a2̌$ will lie on opposite sides of $b1̌$ and $b2̌$, and vice-versa. To simplify the discussion, let’s rotate the plane so that $a1̌$ and $a2̌$ are going ``north’’; then both $b1̌$ and $b2̌$ are going in the general ``east’’ direction, or both are going ``west’’:\fig3

\mfig5
In the first case, the winding numbers with respect to $B$ are one higher in the north side of $b1̌$ and $b2̌$ than on the south; the situation is reversed in the second case. In either case, the winding numbers with respect to $A$ are one higher on the western side of $a1̌$ and $a2̌$ than on the eastern side. The reader can check that, independently of whether the winding numbers are positive or negative, the situation at $x$ in the product will be essentially the same in all cases: one tracing contributes $p+1$ moves coming into $x$ and $p$ going out of $x$, while the other tracing contributes $q$ incoming moves and $q+1$ outgoing ones.
\endmfig

By definition, the turns of $A\cdot B$ at $x$ will be: $p+q$ ``ordinary’’ turns of zero degrees, connecting every incoming move except one to an outgoing move ``straight ahead’’ of it; and an ``extraordinary’’ turn connecting the unpaired incoming move to its outgoing counterpart from the other tracing. The two unpaired moves, and the extraordinary turn connecting them, are adjacent to the quadrant where the winding numbers are highest for both tracings (and for the product).

\mfig3
\digress {As a matter of fact, the way in which we pair incoming and outgoing moves at such vertices is not too important. The pairing obviously does not affect the winding numbers of $A\cdot B$. As for the degree $\delta(A\cdot B)$, it is easy to prove that any other pairing can be obtained from the one we have described by exchanging a ``crossing’’ by a ``bounce’’ as shown at right; and such exchanges clearly do not affect the degree. The main value of the rule we gave is that it shows there is at least one such pairing.}
\endmfig

It is clear from the construction above that every move terminates at the beginning of a turn, and vice-versa; therefore, the result is a properly defined polygonal tracing. The figure below shows a complete example of this construction.\fig4

\theorem{\Theviii}{If $A\cdot B$ is defined, and $p$ is a point not on $A$ or $B$, then $w(p, A\cdot B)=w(p, A)w(p, B)$.}
\proof{Consider a ray $r$, with origin $p$ and oriented away from it, that avoids all vertices of $A$, $B$ and $A\cdot B$ and intersects each edge of the three tracings in at most one point\fig3
Such a ray can always be found, as the vertices and critical directions of the three tracings are finite in number. Clearly, it will intercept only a finite enumber of edges, and it never intercepts an edge of $A$ and one of $B$ at the same point. The proof proceeds by induction on the number of edges of $A$ and $B$ crossed by the ray; the idea is to walk from infinity towards $p$ along the ray $r$, keeping track of how the three winding numbers change at each intersection.\par

\pp If $r$ does not intercept any edge of $A$ or $B$, then it will not intercept any edge of $A\cdot B$; all three winding numbers are zero, and we are done. If it does, without loss of generality we may assume the ray-edge intersection $x$ closest to $p$ is between the ray and one or more edges of $A$ (and perhaps some of $A\cdot B$). Let $q$ be a point on the ray that is beyond $x$ but before the next intersection (if any).

\pp By induction, the theorem is true at $q$, i.e. $w(q, A\cdot B)=w(q, A)w(q, B)$. Let $\alpha$ be the number of moves of $A$ that pass through $x$ going from the right side of $r$ to the left, minus those that pass through it in the opposite direction. By definition, we will have $w(p, A)=w(q, A)+\alpha$, and $w(p, B)=w(q, B)=w(x, B)$. Therefore, the product $A\cdot B$ will contain $w(x, B)$ copies of those $\alpha$ moves of $A$; it folows that
$$\eqalign{w(p, A\cdot B)|=w(q, A\cdot B)+\alpha w(x, B)\cr
\null|=w(q, A)w(q, B)+\alpha w(q, B)\cr
\null|=\biglp w(q, A)+\alpha\bigrp w(q, B)\cr
\null|=w(p, A)w(p, B).\cr}$$}

Let’s emphasize once again that the time reversal of moves and turns reverses only the order in which the states are traversed, not their orientations. Recall also that the orientations of the moves do not affect the winding numbers; therefore, they may be ignored while constructing the product, and just copied at the end.

The multiplication of tracings can be seen as a generalization of the intersection of figures, and in a sense reduces to it for simple enough tracings. It is easy to see why this is true: in the product $A\cdot B$, the only parts of $A$ that survive are those contained in regions of nonzero winding number with respect to $B$, and vice-versa; therefore, the ``interior’’ of $A\cdot B$ is the intersection of the ``interiors’’ of $A$ and $B$. See for example the figure below:\figno(\Figvii)3

The multiplication of tracings is commutative and associative, i.e. $A\cdot B=B\cdot A$ and $A\cdot(B\cdot C)=(A\cdot B)\cdot C$, except that in the second expression it may be the case that only one side is defined (can you think of an example?). Affine maps distribute over multiplication, i.e. we have $(A\cdot B)↑T=A↑T\cdot B↑T$ for any $A$, $B$ and $T$. Multiplication distributes over addition of tracings, that is $A\cdot (B+C)=(A\cdot B) + (A\cdot C)$.

\mfig4
Actually this is not precisely true: $A\cdot (B+C)$ and $(A\cdot B) + (A\cdot C)$ may be different tracings. For example, the tracing $A$ of figure (\Figvii) can be interpreted as the sum of two concentric squares $A1̌$ and $A2̌$ with opposite orientations. If we multiply each separately by $B$, and add the results, we get the tracing shown at right.
\endmfig

Note that all moves and parts of moves that we got in $(A1̌\cdot B) + (A2̌\cdot B)$ but not in $A\cdot B$ are present in two copies, having same orientation but opposite direction of traversal. In the computation of winding numbers, these paired moves always cancel each other, except for points lying on top of them. Similarly, whenever we get an extra turn in $(A1̌\cdot B) + (A2̌\cdot B)$ we also get its time reversal, and they cancel each other in the computation of the degree.

To get a cleaner theory of tracings and convolutions, it seems we should consider those two tracings as equivalent, i.e. ignore differences that result from adding or removing an edge (or turn) together with its time reversal. Adding or deleting such ``null’’ pairs to a tracing $A$ affects its convolution $A\ast B$ only by the addition or deletion of other null pairs.

Note that two moves passing through the same set of points only cancel each other in this way if they have the same orientation and opposite directions of traversal, as in the first pair of the figure below. The other three pairs shown are {\it not} irrelevant: they affect the winding numbers of whole regions and/or the degree of the tracing.\fig3

\digress{The existence of such ``null’’ moves is a sign that we don’t have yet the best definition of tracings; we would like to define them so that ``equivalent’’ means ``equal’’. The decomposition of tracing into tours is another such distracting feature of our definition, which is not essential to the theory.

\dp We should probably define a tracing as a multiset of moves and tours that is ``balanced’’, i.e. that has as many moves coming into a state as there are tours going out of it, and vice-versa. A particularly intriguing possibility is to require all moves and turns to be pairwise disjoint (except for their extremities), and to represent backward moves as forward ones with negative multiplicity. In this representation, a null pair is really ``not there’’ at all.}

When the simplifying assumptions do not hold, the details of the product construction become slightly more complex, but the ideas remain basically the same. In the first place, it is possible for an edge of $A$ to overlap, in whole or in part, with an edge of $B$ (as long as they have the same orientation). In the initial ``edge breakup’’ step, we will not be able to make all edges of $A$ disjoint from those of $B$; we will instead put the breaks so that every edge of $A$ is disjoint {\it or coincident} with any one of $B$.

In the second place, in the original tracings the intersections may occur also between an edge and a vertex, or between two vertices; also, two or more edges of $A$ may intersect $B$ at the same point. The implication of all these facts is that, after the breakup process, there may be any number of edges of either tracing entering and exiting each vertex, each with arbitrary multiplicity.

If an edge $a$ of $A$ is not coincident to any of $B$, then the simple rules given above still apply: the winding number $w(a, B)$ is well defined, and the product tracing will contain that many copies of the move $a$. If $A$ contains $\alpha$ copies of $a$, then this rule applies to each copy in turn, and the product will contain $\alpha w(a, B)$ copies in total.

When two edges $a$ of $A$ and $b$ of $B$ coincide, we need a special rule, since we have assumed the winding numbers of $a$ with respect ot $B$ and of $b$ with respect to $A$ to be undefined in this case. It turn out however that the correct rule is equivalent to assuming the winding numbers to be halfway between those in the two adjacent regions.

For example, let’s say both edges are moving ``north’’, and their multiplicities in $A$ and $B$ are $\alpha$ and $\beta$, respectively. Then we assume $w(a, B)=wB̌+\beta/2$ and $w(b, A)=wǍ+\alpha/2$, where $wǍ$ and $wB̌$ are the winding numbers with respect to $A$ and $B$ of a point $y$ just ``east’’ of both edges. The product tracing then will contain $\alpha (wB̌+\beta/2) + \beta(wǍ+\alpha/2)=\alpha wB̌+ \beta wǍ+ \alpha \beta$ copies of the move $a$. (If the edge $b$ moves in the direction opposite to that of $a$, we take $\beta$ to be negative). A little thought shows how to extend the proof of theorem {\Theviii} to accomodate this special case.\fig3

Compared with the moves, the turns of the product tracing are much harder to describe in detail. The problem is that we may now have any number of moves of $a$ and/or $B$ going into and out of a vertex $x$. If we look at a pair of consecutive moves $a1̌$ and $a2̌$ of $A$, say, their winding numbers with respect to $B$ may differ by more than one; this difference corresponds to the net number of times that $B$ crosses $x$ from one side of $a1̌a2̌$ to the other. Each of these crossing will ultimately contribute one unpaired copy of $a1̌$ (or $a2̌$) to the product tracing. On the other hand, because of $a1̌a2̌$ the winding numbers with respect to $A$ will be one greater on the left side of $a1̌a2̌$; this will cause a surplus of $B$ edges on that side. We will not try to prove it here, but a few examples should convince the reader that the two surpluses can always be matched by ``extraordinary’’ turns.\fig4

This case is further complicated by the possibility of one or more edges of $A$ coinciding with some of $B$, and by the possibility that edges incident to an intersection have zero length. Fortunately, we will use the product of tracings only as a theoretical device, not as a practical one.

The definitions of tracing and convolution we gave above are rather elaborate. Even the lengthy informal discussions that preceded the definitions may be insufficient to justify their adoption. This is even more evident when we consider the peculiar results that convolution gives in some cases, like in the example of page 9.25. This section will be devoted to giving a partial ``justification’’ for those concepts. We will show how the winding numbers $w(p, 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 the original brush-and-trajectory metaphor.

Let’s for a moment forget about tracings, and return to our very first model, in which we considered brushes and trajectories to be nothing more than sets of points of the plane. We had observed that the result of moving a brush $\BB$ along a trajectory $\AA$ was to blacken all points of the form $a+b$, where $a\in \AA$ and $b\in \BB$. There is another interesting way to look at this result:

This lemma is trivial, but it has an important consequence. Recall that $B↑{p\, -I}$ is the brush $B$ rotated $180\deg$ and placed at point $p$; it is then easy to prove the following result:

The interpretation of $A\ast B$ we are going to give next will be basically an extension of theorem {\Thex} to polygonal tracings, with some modifications. It is not enough for us to know whether $p$ 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 $w(p, A\ast B)$. In order to do this, we will have to replace the yes-no test ``$\AA\inte\BB↑{p\,-I}\neq\ety$’’ by one giving an integer result.

To gain some intuition about what this test should be, let’s consider the example below, in which the brush $B$ is a circle\foot\dag{Even though we defined convolution only for polygonal tracings, we will apply it informally also to circles and other smooth figures, which are somewhat simpler to draw and analyze. The concepts of continuous tracings and their convolution can also be formally defined; for our purposes, however, it suffices to think of such figures as polygonal traces consisting of a large number of small moves.} of radius $r$, and the trajectory $A$ is a pair of circles of radius $R>r$ placed less than $2r$ away from each other. All circles are oriented and traversed counterclockwise.\figno(\Figviii)4

The convolution of the two tracings will be a pair of circles of radius $R+r$, as shown above; the numbers in the figure show the values of $w(p, A\ast B)$ in each ``region’’ of the tracing. Now let’s try to see how those numbers could arise from the construction suggested by theorem {\Thex}; i.e., let’s take a point $p$ in each of the four regions above, and see how the inverted and displaced tracing $B↑{p-I}$ is related to $A$:\fig4

We can see that a point $p$ with $w(p, A\ast B)=k$ ($k=0, 1$ or $2$) is one for which $A\inte B↑{p-I}$ has exactly $k$ components. This result may be false (or even meaningless) for more exotic tracings, but it is on the right track: with only a little more elaboration, it will give us a precise expression for $w(p, A\ast B)$. We only have to 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 9.5. Therefore, we are ready to restate theorem {\Thex} in the language of polygonal tracings:

\theorem{{\Thexi} {\rm (The convolution theorem)}}{If $A$ and $B$ are two transverse polygonal tracings, then $w(p,A\ast B) = \delta(A\cdot B↑{p-I})$, for all points $p$ where both numbers are defined.}\par

Recall that $B↑{p-I}$ is the tracing obtained by rotating $B$ by $180\deg$ and translating it so that its origin is moved to point $p$. It is important to note that this operation rotates the orientations and positions of all states, moves, and tangents, but preserves their order of traversal; therefore, forward moves remain forward, counterclockwise turns remain counterclockwise, and $w(q, B)$ is equal (including sign) to $w(p-q, B↑{p-I})$. Recall also the discussion accompanying example (\Figviii).

Note that if we think of $A$ and $B$ as fixed and $p$ as variable, then both sides are defined, except for a set of points $p$ of measure zero. The product is undefined when $A$ and $B↑{p-I}$ have an improper intersection $x$; this means there are two opposite states $a$ of $A$ and $b↑{p-I}$ of $B↑{p-I}$ with same position $x$. Said in another way, there are two parallel states $a$ of $A$ and $b$ of $B$ such that $\stpos a= x= p-\stpos b$, i.e. $p=\stpos a+\stpos b$. This is precisely the condition for $p$ being on the convolution $A\ast B$, so the two sides of the equation are undefined for exactly the same points.\fig3

Note also the formal analogy of this result with the definition of the convolution of sequences: the
convolution $\langle cň\rangle$ of $\langle pň\rangle$ and $\langle pň\rangle$ is defined by the equation $cň = \sumǩ pň q{̌n-k}$.

We will not attempt to prove the fundamental theorem in these notes. Instead, we will apply it to some of the examples we have presented before. Let’s consider first example (\Figii), the convolution of a circular brush $B$ of radius $r$ with a trajectory $A$ of radius $R>r$. As we know, the convolution is simply a circle of radius $R+r$. \fig4

\mfig4
Since $B$ is center-symmetric, $B↑{p\,-I}$ is simply $B$ placed with its center at $p$; this may result in three distinct situtations. If the distance between $p$ and the origin is more than $R+r$, as shown at right, the winding number of $p$ with respect to $A\ast B$ is zero, and the product of $A$ and $B↑{p-I}$ is empty and has degree zero.
\endmfig

\mfig4
If the distance from $p$ to the origin is less than $R+r$, but more than $R-r$, then $B$ reversed and placed at $p$ intersects $A$. The product $A\cdot B↑{p-I}$ consists of the lens-shaped figure shown at right; its degree is 1, matching the winding number of $p$ with respect to $A\ast B$.
\endmfig

\mfig4 Finally, if $p$ is close enough to the origin, $B↑{p-I}$ is entirely inside $A$. The product consists of $B↑{p-I}$ itself, whose degree is $1=w(p, A\ast B)$. Note that the product is undefined only when $B↑{p-I}$ is touching $A$ from the outside, i.e. when $\dist(p, o)=R+r$. This is precisely the condition for $p$ to be on $A\ast B$.
\endmfig

A more interesting example is that of figure (\Figv): a square (without its interior) convolved with the circular brush. As before, we represent the first by two square tours $A1̌$ and $A2̌$ with identical dimensions and positions but oriented and traversed in opposite directions. In computing $A\ast B$, it is best to use distributivity, computing $A1̌\ast B$ and $A2̌\ast B$ and then add the results.\fig4

\mfig4
The convolution $A1̌\ast B$ is not much different from the previous example: the result is a square with rounded corners. The convolution with the clockwise square $A2̌$ gives the other tracing shown above. Let us understand, in terms of the fundamental theorem, what happens as we place the brush $B↑{-I}$ at various points $p$ in the plane with respect to $A$. It is clear that if $p$ is too far out, as shown at right, the product is empty. the $B↑{-I}$ traversed clockwise, i.e, a loop of degree -1.
\endmfig

\mfig4
Simlarly, if $p$ is close enough to the origin, the brush lies entirely inside the square, and the product is $B↑{p-I}$ traversed in the opposite direction. The degree of this tracing is -1, matching the winding number of $p$ in $A2̌\ast B$.
\endmfig

\mfig6
But what about the case shown at right? Now the brush cuts off a piece $c$ of the upper side of the square. Notice that in the product $c$ retains its direction of motion, while that of $d$, the portion of the brush within the square, reverses. So it appears that the product is a clockwise loop, whose degree is $-1$. Something must be wrong, because the winding number of $p$ in $A2̌\ast B$ is zero! The answer is that, although the arc $d$ was time-reversed, its orientation is still the same. The turns at the two corners $A$ and $B$ will be as shown. If we keep a careful account of the directions swept by the orientation vector as we go around the product tracing, we see that the degree (net number of times a particular direction is traversed counterclockwise, or net number of counterclockwise $360\deg$ revolutions) is actually zero, as it should.
\endmfig

\mfig5
The most complex situation that shown here, in which the circle $B↑{p-I}$ cuts off two consecutive sides of $A2̌$, but misses the corner. Study the illustration shown carefully. First check that the winding number $w(p, A2̌\ast B)$ is 1. Next, check the directions of motion, orientations and turns shown for the product $A2̌\cdot B↑{p-I}$. Finally, compute the degree of the product: be sure you understand why the car has made a total of one $360\deg$ counterclockwise revolution, so the degree is also 1.
\endmfig

\mfig6
From the point of view of the fundamental theorem, the main novelty is what happens at the intersections between the brush and the path. Notice that in the general case shown at right the circle $B↑{p-I}$ cuts the path in two arcs with opposite orientations and directions of traversal, and we must consider the path $A$ as cutting off from the circle two arcs of length zero. Each of the intersection points should be seen as a pair of coincident ones; there the tracing switches from the path to the circle and then to the other arc of the path. Even though the arcs of $B↑{p-I}$ have zero length, they have a definite orientation, and force the turns at the intersections to be all counterclockwise. The result is again doubled-up path, similar to $A$, that has degree 1.
\endmfig

\mfig4
Perhaps this result will seem more natural if we imagine the two sides of the path have been pulled slightly apart, transforming it into a narrow counterclockwise loop. The reader may enjoy checking that the degree of the product would still be 1 if the two branches were pulled apart the other way, so as to give a clockwise loop, or randomly interwowen as shown at right (be careful with the orientations!).
\endmfig