\input TR10GBWideFormat

\begfile{GBb09.tex of October 17, 1983 4:31 pm --- Stolfi}

\chapter{9}{Tracings}


% additional macros

\def\A{\hbox{\bf A}}
\def\B{\hbox{\bf B}}
\def\T{\hbox{\bf T}}

\def\Figi{F1} % Better use mnemonics, eg \FigBgCirXSmDisk
\def\Figii{F2}
\def\Figiii{F3}
\def\Figiv{F4}
\def\Figv{F5}
\def\Figvi{F6}
\def\Figvii{F7}
\def\Figviii{F8}
\def\Figix{F9}

\def\larc{\,\null^{+}\,} % counterclockwise arc
\def\rarc{\,\null^{-}\,} % clockwise arc

\def\Knu{Knu}

\section {9.1. Introduction}


We will devote this chapter to what may seem at first glance a rather specialized topic, namely the concept of {\it polygonal tracing} and the {\it convolution} of such tracings. The ideas to be presented are both interesting in themselves and have a numerous applications in computational geometry. But our main reason for including them at such an early stage is that they lead naturally to some not-so-obvious but very powerful concepts, like the two-sided plane and geometric duality, that will form a recurrent theme throughout the rest of the course.

We will begin by a very practical problem that arises in connection with computer graphics and typesetting, that of two-dimensional {\it shape description}. Currently much of high-quality computer printing is being produced by {\it raster devices}, which consider a page as a two-dimensional array of tiny dots or {\it pixels}, each to be painted either black or white. When using such devices, the information to be printed must be ultimately encoded as a two-dimensional array of bits, each specifying the color of the corresponding pixel.
\figspace 3.5cm % the letter "a" with an enlarged portion showing pixels, and corresponding part of bitmap.

This encoding allows complete freedom in the placement of characters, in the choice of fonts and symbols, and in the intermixing of text and figures; but it is not without its drawbacks. One of the most serious is the sheer size of the bit arrays: a page printed in a raster device of typical resolution contains over five million pixels, and a high-quality printer may use more than fifty thousand pixels for each of the letters in this sentence. The handling of such raster images makes heavy demands on computer memory and time. Human interaction in the creation and manipulation of such huge arrays is also clearly problematic. A final problem is that images encoded in this format cannot be easily rotated,  scaled, or otherwise geometrically tarsnformed.

These problems make it desirable to represent the images to be printed in some other form, and only convert it to raster format just before printing. It turns out that many of the images printed in typesetting systems consist of collections of solid black ``patches'', each covering a large number of pixels but having a relatively simple boundary. That is the case, for example, with most text (composed of characters and symbols) and technical line drawings (consisting of lines of varied width and shape, dots, and other geometrical figures).

\mfig 4cm % the outline of an "a" showing separate arcs.
It is therefore natural to represent each of those patches by a description of its idealized outline, with the convention that its interior should be painted black. The outline can be described as a simple polygon, as an algebraic or parametric curve (e.g., a circle), or by any other suitable method. For example, a widely used technique is to represent the outline as a {\it cubic spline}: a collection of one or more arcs, each of them a parametric cubic of the form $p(t)=at^3+bt^2+c+d$, where $t$ ranges from $0$ to $1$ and the coefficients $a, b, c$ and $d$ are planar vectors. Many of the characters on this page you are now reading were encoded in exactly this way.
\endmfig

The widespread use of this {\it outline method} for representing the shape of patches attests to its effectiveness. The outline description of a figure is independent of the resolution of the printing device, and in most cases it is more compact than the corresponding bit array. Operations such as scaling, rotation, and slanting of characters can be performed by simply applying them to the outlines. There are many algorithms for converting outline descriptions into bit arrays; some of these are efficient enough for the conversion to be performed at the printing device itself, concurrently with the actual printing of the image.

Yet, the outline method is not without its problems. Many of the basic shapes occuring in text characters and in technical drawings are most naturally described as lines of constant width whose midline follows some specified trajectory. This is the figure that would be painted if we were to follow the given trajectory with a circular ``brush'', i.e., one which leaves a circular spot of constant radius every time it is placed down on the plane.  An example is the ``sausage'' of the illustration below. By using brushes with non-circular shapes one can obtain interesting calligraphic effects with very little effort, like the varying width of the strokes in the letter ``o'' shown below.
\figspace 4cm% A curved line drawn with circular brush; a letter "o" with elliptical slanted brush.
Some startling effects can be obtained by allowing the brush to rotate or change shape as it moves along the trajectory; however, these extra degrees of freedom make the manipulation of brush-and-trajectory descriptions more complex and time-consuming, and the machinery we would need for their theoretical treatment would lead us too far beyond our goals. Therefore, we will restrict our discussion to the case in which {\it the brush shape and orientation is the same at all points of the trajectory}.

Experience has shown that this {\it brush-trajectory} method for shape description is quite convenient to use; for example, the METAFONT system for font design developed by D. E. Knuth is entirely based upon it. Unfortunately, the brush-trajectory representation is much harder to convert into the bit array format. Consider this straightforward algorithm: we place the brush on successive positions along the trajectory, spaced closely enough that the motion appears continuous at the device's resolution; and, for each position, we set to ``black'' all bits of the array corresponding to pixels covered by the brush. This algorithm may set each bit a large number of times (about the diameter of the brush in pixels), and therefore is too inefficient for high-resolution devices. It is possible to improve its performance by ``painting'' at each step only the pixels that were not covered by the preceding placement of the brush; but this usually requires each pixel to be set individually, so the improvement is not enough to make the algorithm competitive with those working with the outline representation.

Furthermore, there are many shapes that are better described by the outline method, and many algorithms that produce an outline representations from a bit arrays (like the ones that are obtained by digitizing an existing image from paper or film). These considerations suggest that we retain the brush-trajectory metaphor for the high-level description of shapes, but use the outline metaphor as the standard internal format, and as an intermediate step in the construction of the bit arrays.

The purpose of what has been said so far, and in particular of the last paragraph, is to motivate the problem we will be discussing for most of this chapter: that of converting a brush-trajectory description into the corresponding outline representation. The approach we will follow, and the main results we will see, are mostly due to Lyle Ramshaw. Most of this work is quite recent and in fact the particular development for polygonal trajectories we will follow is only a few weeks old. This may help explain, albeit not justify, the roughness of these notes.

\section {9.2. The slope lemma}


To get a better understanding of the brush-trajectory metaphor, let's begin with a simple example: a circular brush $\B$ of radius $r$ moving along a circular trajectory $\A$ of radius $R$, $R>r$.
\numfig 3cm{(\Figi)}
When the center of the brush is at some point $a$ of $\A$, it will cover all points that are at distance $\leq r$ from $a$; the resulting shape will be a circular annulus, with inner radius $R-r$ and outer radius $R+r$. This set of points can also be expressed as
$$\A\oplus\B=\rset{a+b \relv t\in \A\,\, \and\,\, b\in \B}\eqno(1)$$
and it is clear that this formula holds for any trajectory $\A$ and brush $\B$, provided the brush does not rotate or change shape as it moves along the trajectory. Note that equation (1) is symmetrical in $\A$ and $\B$; that is, the resulting figure is the same, whether we move the brush along the trajectory or the trajectory along the brush!

For this observation to make sense, we must consider first what it means to move a figure along a ``trajectory'' that contains interior points; we take this to mean simply that the brush is to be ``placed down'' at all points of the trajectory, independently of whether they are on the boundary or in its interior. If in the previous example the trajectory were to be taken as the big circle {\it with its interior}, then the result would have been a full disk of radius $R+r$, with no hole.
\numfig 5cm{(\Figii)}

Another immediate consequence of equation (1) is the following lemma, whose proof is trivial:

\lemma{\The1}{if $\A$ and $\B$ are translated in the plane by the vectors $b
0$ and $a
0$, respectively, the resulting figure will be $\A\oplus\B$ translated by $b
0+a
0$.}

In most cases, this lemma allows us to ignore the exact position of the brush and trajectory with respect to the origin, since they do not affect the shape of the result.

Let's now try to characterize the boundary of the resulting figure. By looking at the previous examples, one soon discovers the following property:

\mfig 4cm
\lemma{\The2}{Every point on the boundary of $\A\oplus\B$ has the form $b+a$, where $a$ and $b$ are {\it boundary} points of $\A$ and $\B$.}
\proof{If $b$, say, is an interior point of $\B$, and $S
b\subset \B$ is an open ball centered at $b$, then for any point $a$ of the trajectory the point $a+b$ will be surrounded by the ball $a+S
b\subset \A\oplus\B$, i.e. $a+b$ will not be on the boundary of the resulting figure. A similar argument holds if $a$ is an interior point of $\A$.}
\endmfig

This lemma is quite interesting, for it establishes a connection between the brush-and-trajectory metaphor and the one based on outlines: it suggests that the outline of $\A\oplus\B$ can be computed from those of $\A$ and $\B$. Unfortunately, it holds only in one direction: even if $a$ and $b$ are boundary points of $\A$ and $\B$, $a+b$ may not be on the boundary of $\A\oplus\B$.

\mfig 4cm
Let's look again at the example of figure (\Figi), and try to follow some point $b$ on the boundary of the brush, e.g. at its very top, as the latter moves along the trajectory. It is clear that as long as the brush is moving vertically or diagonally, the ``trace'' left by $b$ will be completely surrounded by the traces of the brush points in an immediate neighborhood of $b$. Therefore, the only points of the trace of $b$ that can be on the boundary of $\A\oplus\B$ are those corresponding to instants where the brush was moving horizontally.
\endmfig

By repeating the same argument for other points on the boundary of $\B$, we conclude that $a+b$ will be on the boundary of $\A\oplus\B$ only when the tangent to the trajectory at $a$ is parallel to the tangent to the brush at $b$. For each $a$, there will be exactly two antipodal points $b$ for which this happens; and these will give rise to exactly two points on the boundary of $\A\oplus\B$, one on each of its two circles. So, at least for the first example, we have got a complete characterization of the boundary points of $\A\oplus\B$: they are obtained by adding every boundary point of $\B$ with every boundary point of $\A$ subject to the condition that the tangents at these points have the same slope.

Now this is the kind of result that we are looking for. Clearly, the argument invoked to show that the tangents at $b$ and $a$ must be parallel does not use the fact that the curves in question were circles, so the same conclusion must be true for arbitrary curves. Let us then cede to the temptation, and adopt for our consideration\foot{1}{The original meaning of the word ``theorem'' was ``something to be considered''.} the following:

\theorem{{\The3} {\rm (Slope Theorem)}}{Let $\A$ and $\B$ be the figures defined by the outlines $A$ and $B$, and let $A\ast B$ be the set of all points $b+a$ such that $a\in A$, $b\in B$, and the tangents to $A$ and $B$ at those points are parallel. Then the figure described by $A\ast B$ is $\A\oplus\B$.}

The operation $A\ast B$ defined by the construction above is called the {\it convolution} of the outlines $A$ and $B$.

\section {9.3. Directed outlines and winding numbers}


As soon as we try it on other examples, our precious ``theorem'' seems to come apart at every joint. Just to mention one problem, consider what happens in figure (\Figii), where the trajectory too is a full disk. The outlines $A$ and $B$ are the same as those of figure (\Figi), and therefore their convolution $A\ast B$ should also be the same. However, as we already remarked the resulting figure is now a solid disk of radius $R+r$, and the inner circle defining the annulus has mysteriously disappeared!

After contemplating this failure (and quite a few that are even worse), an honest mathematician would try to reformulate theorem {\The3} so as to exclude pathological cases and/or relate $A\ast B$ and $\A\oplus \B$ in some other way. However, if we were to follow this course of action, we would end up with a theorem weak and complicated to the point of being almost useless. Rather than doing so, or calling it quits and moving to some other topic, we will spend the next couple of sections ``fitting the shoe to the foot'': i.e., trying to patch up the definitions of ``outline'', ``tangent'', ``interior'', and ``convolution'' so as to make theorem \The3, or something as near it as possible, true.

With regards to the example of figure (\Figii), we can claim that the problem is not with theorem \The3, but with the fact that the boundary of a figure does not contain enough information to distinguish a solid circle from an empty one. Therefore, we have to extend the definition of ``outline'' so as to include this information.

\mfig 5cm
One way of doing this was already used implicitly in the annulus of figure (\Figii). We considered the points within the inner circle as being  ``outside'' the annulus, in spite of they being entirely surrounded (twice) by its outline. This interpretation is compatible with the intuitive idea that whenever we cross any portion of the boundary, we move from the interior to the exterior or vice-versa. So, if we make the convention that points sufficiently far away are outside the figure, we can decide whether a point is inside or outside by counting how many times a ray coming out of that point crosses the outline, and checking whether this number is odd or even, respectively. If the point lies on the outline itself, it is of course neither inside nor outside, but on the boundary of the figure.
\endmfig

According to this idea, the outline of an empty circle should be that of an annulus of zero width, i.e., should consist of two copies of the same circle. Following the criterion above, we see that this outline has no interior points, only boundary ones. As before, the outline of a solid disk is just a single circle.

Even though this revised definition of outline can distinguish between solid and empty figures, it makes theorem {\The3} even less true. It still fails in the example of figure (\Figii): the convolution of the outlines still includes the inner circle $R-r$, corresponding to an annulus instead of the correct full disk of radius $R+r$. And now it fails also in example (\Figi): the double outline of $\B$ produces two copies each of the inner and outer circle in the convolution. The corresponding figure has {\it no} interior points, and is simply a pair of concentric, empty circles.
\figspace 3.3cm

\mfig 5cm
Fortunately, there is a second way of defining outlines and interiors, one that works much better and is almost as natural as that considered above. In this definition, each closed curve that is part of an outline $A$ is assigned a {\it direction of traversal}. The {\it winding number} of a point $p$ in the plane with respect to $A$, denoted by $w(p,A)$, is defined by taking a ray coming out of $p$, and counting how many times the ray crosses $A$. Unlike the previous definition, we count a  crossing as $+1$ if $A$ is at that point directed counterclockwise, and $-1$ if it is directed clockwise (as seen from $p$).
\endmfig

It can be shown that the winding number depends only on $p$ and $A$, and not on the particular ray used. Intuitively, the winding number is just the signed total of the complete turns made by the outline around the point $p$ (with each turn counted as $+1$ or $-1$ depending on its direction). The exterior of the figure described by the outline is, by definition, the set of those points with zero winding number. Points with nonzero winding numbers are interior. If a point $p$ lies on the outline itself, its winding number is undefined; in that case $p$ may be either in the interior or on the boundary of the figure (topologically speaking), depending on whether it is adjacent or not to its exterior.

According to these ideas, we can describe a solid circle, like the brush $\B$ in example (\Figi), by a single copy of its boundary, traversed in the counterclockwise direction; the winding number then is 1 inside the figure and 0 outside. The annulus of example (\Figi) can be described by a counterclockwise circle of radius $R+r$ and a clockwise one of radius $R-r$. The empty circle  $\A$ can be described as the limiting case of an annulus of zero width, i.e. by two copies of a circle of radius $R$, traversed in two opposite directions; this will give zero winding number everywhere, except on the circle itself.
\figspace 4cm

Are those changes effective in making theorem {\The3} work, at least for the examples (\Figi) and (\Figii)? The answer is ``yes'', provided we take a further precaution: when matching points to compute the convolution, we require that the tangents at those points be parallel {\it and the directions of traversal be the same.} We can think of the tangents as being oriented in the same direction as the curve at the point of tangency; therefore, our rule is that we match points where the {\it oriented} tangents are parallel, i.e., they are pointing in the same direction. This gives also a rule for assigning a direction of traversal to the convolution: the direction at point $a+b$ is that of the tangents to $A$ and $B$ at $a$ and $b$.

Let's consider example (\Figii) under this new interpretation. Now, each point $a\in A$ can be matched with exactly one point $b\in B$; therefore, $A\ast B$ consists of a single circle of radius $R+r$, oriented counterclockwise. The figure described by this outline is the solid disk of the same radius, which is exactly $\A\oplus\B$.
\figspace 4cm

In example (\Figi), recall that the outline of the trajectory consists of two copies of a circle of radius $R$, oriented in opposite directions. The counterclockwise copy will give rise\foot1{Wise are the clocks that turn counterclockwise and despise the counterclocks that do otherwise.} in the convolution to a similarly oriented circle of radius $R+r$, as in example (\Figii). The other copy will give a different result: a point $b$ of the brush will match the point $a$ of the trajectory that is in a position ``antipodal'' to that of $b$. If the coordinates of $b$ are $(0, r)$, $a$ will be $(0, -R)$; if $b$ is $(r, 0)$, $a$ will be $(-R, 0)$, and so forth. The result will be a circle of radius $R-r$, and it will be oriented clockwise. One can readily check that these two circles are a correct outline representation of the annulus $\A\oplus\B$.

As a further test, let's consider what happens in example (\Figi) if the radius of the brush is larger than that of the trajectory, i.e. if $r>R$. From equation (1) (and from the intuitive interpretation) we would expect the resulting figure to be a black disk of radius $r+R$, instead of an annulus.
\numfig 4cm{(\Figiii)}
And that is precisely what we get from the convolution of the outlines: $A\ast B$ still consists of two circles, one of radius $r+R$ and the other of radius $r-R$; however, now both are oriented counterclockwise, so the winding number of a point within the inner one is 2, not 0. Therefore, the figure described by $A\ast B$ is the whole disk of radius $r+R$.

\section {9.4. Corners, turns, and reverse gear}


Encouraged by the successes obtained so far, let's now test theorem \The3 on some nastier cases. Let's keep the same brush (a full circle of radius $r$), but use for trajectory a square of side $2L$, $L>r$, together with its interior. It is easy to see that $\A\oplus\B$ is a square with side $2(L+r)$ and rounded corners.
\numfig 3cm{(\Figiv)}

\mfig 4cm
As we try to compute the convolution, we run immediately into trouble. The only tangents to the trajectory are the vertical and horizontal lines containing its sides, and therefore the convolution contains only the straight portions of the desired outline; since that is not a closed curve, winding numbers with respect to it are undefined, and so is its interior.
\endmfig

\mfig 6cm
The fix to handle this case is almost obvious: we have to extend the definition of tangent so as to include the lines passing through the corners of the square but avoiding its interior. We may think of tangents as being defined by a car that performs a circuit of the outline in the specified direction of traversal: the tangent at each point is the oriented line passing through the car and pointing in the same direction the car is facing. While moving along a side of the square, the car keeps facing the same way, and so the tangent stays fixed. When it reaches a corner, the car stops moving, and begins to turn; threfore, at each corner there will be an infinity of tangents, corresponding to all the directions in which the car faces while making the turn.
\endmfig

When the car arrives at a vertex, it must switch from the arriving direction to the departing one. The car has the choice of turning either to the left or to the right; since these two alternatives give rise to different sets of tangents at the corner, we must choose among them in some way. In the case of the square, we could rule out the second alternative (turning right by $270\deg$) on the grounds that the tangents determined in this way cut through the interior of the figure. But this rule is insatisfactory in general; apart from depending on a ``global'' property of the outline (its interior), it maybe the case that {\it any} line through a point of the boundary meets the interior of the figure.

A second alternative is to establish the convention that the car always turns in the direction that gives the smallest angle of turn, i.e. the one that is less than $180\deg$ (ignoring the sign). This definition would work for the square, and for almost all practical cases; indeed, in many aspects this definition is the most natural one. There is still an ambiguity, however, in the case the directions of arrival and departure are exactly opposite to each other: we have to choose between turning left or right by $180\deg$, and each choice will give a different set of oriented tangents at the corner\footfig 3cm1{Such cases cannot be treated as degenerate, for they arise when the trajectory is a line segment (straight or curved) that does not close upon itself: the outline of such a trajectory must traverse the line in one direction, turn back at its endpoint, and traverse it again in the opposite sense.}. Therefore, we will be conservative and assume that {\it the direction in which the car turns at each corner is part of the outline description}. In the illustrations that follow, we will indicate the direction of turn by a `$+$' or a `$-$'  (for ``left'' and ``right'', respectively) next to each corner; if these signs are omitted, it is assumed the car turns according to the smallest-angle rule.

Let's see if these rules take care of example (\Figiv). If the car turns left at some vertex $a$ of $A$, say the upper left one, then the tangents at that vertex are all the lines through $a$ that point in the generic ``southwest'' direction. So, $a$ can be matched with all points of the upper left quarter of $B$. These pairs will give rise to the rounded upper left corner of the boundary of $\A\oplus\B$. A similar thing happens at the other three corners of $A$; the convolution then becomes a closed curve, oriented counterclockwise, which is precisely the outline of $\A\oplus\B$.

Let's not speak of victory yet! The worst is still to come, in the guise of example (\Figv): our old and proven circular brush of radius $r$ meets its new rival, a square trajectory $\A$ of side $2L$ with {\it empty} interior. We want the resulting figure $\A\oplus\B$ look as shown below: the same rounded square of example \Figiv, but with a square hole of side $2(L-r)$ at is center.
\numfig 4cm{(\Figv)}

The outline of $\A$ is, of course, two copies of the square, oriented in opposite directions. The counterclockwise copy will correctly produce the outer boundary of the figure, as in the previous example; but the clockwise copy will give rise to the puzzling, self-intersecting ``curve'' shown above.

\mfig 5cm
What is disconcerting about this curve is that the ``direction of traversal'' that we get at each point $a+b$ by simply copying the direction of the tangents at $a$ and $b$ is inconsistent: at each of the eight cusps, we either have two branches of the curve coming in and none going out, or vice-versa. Among other problems, this makes it impossible to assign winding numbers to the points of the plane; for example, a vertical ray coming out of point $p$ in the figure would give a winding number of 0, while one directed $45\deg$ down to the right would give a winding number of 2.
\endmfig

\mfig 4cm
Clearly, we can't assign to $b+t$ the same direction of traversal of $a$ and $b$; we need some better rule that assigns the consistent directions to all points of each closed curve in the convolution. What is unclear is the nature of such a rule; it cannot be arbitrary, for reversing the direction of a single curve in a multi-curve outline may substantially change the interior of the figure it describes (there is no problem, of course, in reversing simultaneously the direction of {\it all} loops).

But suppose we succeed in contriving a suitable rule, which assigns to the curved parts of the inner curve in example (\Figv) a direction of motion compatible with that on its straight parts (i.e., clockwise). Apparently, all would be well: the winding numbers would be 0 inside the central square, 1 between the two curves, and 2 inside the ``ears'' of the inner perimeter, giving the correct figure.
\endmfig

Let's now try to use that shape as the trajectory, and convolve it again with the same circular brush (to make things simpler, assume $L>2r$). A moment thought shows that the result must be similar to that of example (\Figv), except that the thickness of the sides is $4r$ instead of $2r$, and the round corners have radius $2r$ instead of $r$.
\figspace 4cm Indeed, by formula (1) we see that $(\A\oplus\B)\oplus\B=\A\oplus(\B\oplus\B)$, i.e. the result is the same as that of moving a circular brush $\B\oplus\B$ of radius $2r$ along the square trajectory $\A$. However, the outline $(A\ast B)\ast B$ comes out quite different from $A\ast (B\ast B)$:
\figspace 4cm

In fixing the direction of traversal of $A\ast B$ above, we have arbitrarily assumed that the car turns right by $180\deg$ at each cusp. We will not try the other possible combinations of right and left turns, since they will not help; no matter in which direction the car turns at a cusp of $A\ast B$, that cusp will be matched with a whole half-circle of $B$, and will give rise to a similar half-circle segment in $(A\ast B)\astB$ that does not appear in $(B\ast B)\ast T$.

This may seem a minor problem: even though the winding numbers of the two outlines are different for some points of the plane, they still describe the same figure. Unfortunately, the non-associativity of $\ast$ illustrated by the above example would cause serious problems in the formal treatment of outlines and convolution, and would make these concepts much less interesting outside the typesetting context.

Let us revert to orienting the tangent at $a+b$ in the same direction as the tangents at $A$ and $b$. Look again at what happens with example (\Figvi).
\numfig 4cm{(\Figvi)}

As we see, orientations work best if the tangents in the obnoxious arcs of $A\ast B$ are oriented clockwise as seen from the center  of the figure. On the other hand, the only sensible way to fix the winding numbers seems to be to assign to those arcs the opposite direction of traversal. How are we to resolve this dilemma?

The solution is to have it both ways: we have to get used to the idea that {\it the orientation of the tangent(s) at each point of the outline is independent of the direction in which the outline is to be traversed}. In the car analogy, we may think of the orientation of a tangent as giving the {\it direction towards which the car is facing} at some instant; the car may be either ``moving forwards'' (in the same direction it is facing), ``backing up'' (moving in the opposite direction), or turning at a corner while standing still.

\mfig 5cm
For example, a valid traversal of the the inner perimeter of $A\ast B$ in figure (\Figv), could begin with the car at, say, some point $a$ in the upper horizontal segment; at that moment the car would be facing to the right and moving forwards. Upon reaching the first cusp at $b$, the car reverses its gear (without turning!) and backs up along the adjacent quarter circle. As it reaches the second cusp $c$, it begins again to move forward (again without turning) and proceeds down along the right vertical segment $d$. After repeating this maneuver three more times, the car will be back at $a$, still facing to the right.
\endmfig

The direction in which the car is facing at any given instant is not to be confused with the direction in which it is moving: the two vectors are collinear, but the second may be pointing opposite to the first, or may be zero. When computing the winding number of a curve with respect to a point, only the direction of movement is taken into account, and the way the car faces is irrelevant. Conversely, when computing the convolution of two outlines $A$ and $B$, we match all instantaneous positions of the car traversing $A$ with those of the car traversing $B$ where the two cars are parallel and facing in the same way, whether they are moving in the same direction or not. In the illustrations, we will use solid arrowheads ($\lpoint$) to denote the way the car is facing while traversing each portion of the outline, and normal arrowheads ($\scriptstyle >$) to denote the direction of motion. At the corners, the car turns (changes the way it is facing) while standing still; the direction of motion there is undefined, and is replaced by the direction of turning ($+$ or $-$).

As a consequence, in the definition of $A\ast B$ it is not enough to describe the set of points on the resulting outline. We have to describe the convolution too in terms of a collection of car trips; i.e., we must give a rule assigning to each point of the convolution both an orientation ($\lpoint$) and a direction of motion or of turning ($\scriptstyle >$, $+$, $-$), in a consistent way. The orientation is not a problem: every point of the convolution is the sum of two points of $A$ and $B$ where the cars face in the same direction, so we just assign that same orientation to their sum. This rule allows us to obtain the set of all {\it car states} of the convolution, where a car state specifies both an instantaneous position of the car and a direction in which it is facing. Two states {\it match} if the cars are pointing in the same way, irrespective of their positions; therefore, the states of the convolution are obtained by adding (vectorially) the positions of matching states in $A$ and $B$, and retaining their orientations.

\mfig 5cm
To specify completely the convolution as a set of car trips, we have to divide this set of car states into separate loops, and order the elements of each loop in a consistent chronological order. For example, suppose we have matched the two pairs of car states $(a,b)$ and $(a\pr, b\pr)$, where $a$ and $a\pr$, as well as $b$ and $b\pr$, were infinitesimally close in time in the their respective outlines. How should the car move in the convolution: from $a+b$ to $a\pr+b\pr$, or vice-versa?
\endmfig

Note that the directions of motion or turning at $a$ and $b$ may not agree: it may be the case that the state $a$ precedes $a\pr$ in time, but $b$ follows $b\pr$. In such circumstances, we have to choose which of the two should the convolution agree with. We cannot make an arbitrary choice at every state of $A\ast B$, since the directions of motion for all car states on the same loop must be consistent with each other. Neither can we choose arbitrarily a direction for one state on each loop, and let the rest follow by continuity, since, as we remarked, reversing the direction of motion of only one loop may change drastically the figure defined by the outline.

Come to think of it, why should we expect $a+b$ and $a\pr+b\pr$ to be on the same loop of $A\ast B$? Indeed, why do we expect $A\ast B$ to be a nice set of loops, without isolated points, dead alleys, junctions with odd degree, solid patches, and so forth? These are important questions; but, before we try to answer them, let's introduce an interesting mathematical puzzle that hopefully will allow us to better appreciate the subtleties of the problem.

\section {9.5. The Mountaineers' Problem}


Alice and Bob, expert mountaineers and ardent lovers, live in two coastal cities that are separated by the forbidding peaks of the Slope Range. On a fine Saturday morning, they both set out for the mountains, having decided to meet each other by the shortest possible route --- namely, along the straight line connecting the two cities.
\numfig 3cm{(\Figviii)}

For communicating with each other, they carry a pair of portable neutrino radios. Actually, Alice and Bob love each other so much that they can't stand being out of touch even for a single moment:  they will spare neither time nor effort as long as they can keep talking continuously during their journey.

Now the reader must surely know that two neutrino radios can talk to each other only if they are at exactly the same height above sea level. So, Bob and Alice must keep continuously the same altitude, moving up or down always at the same rate. We can ask, under what circumstances are they able to meet in the end and live happily ever after? What strategy should they follow to reach this goal? The reader is urged to try answering these questions (and check the answers against the mountain profile shown above) before reading any further.

\vskip1in
\ctrpar\textwidth pt{\flower}
\vfill\eject

If you have managed to get Bob and Alice to meet across the Slope Range, you must have noticed that their trips are far from being simple. You probably noticed that at times Bob or Alice are moving in the ``wrong'' direction, away from his/her partner; indeed, there are moments where they are both moving away from each other!

To see what is going on, we will construct a chart that will show simultaneously all legal positions and movements of the two loving mountaineers. Let the distance between the two cities be exactly one randometer; then a point along the trail of Alice or Bob can be represented by its horizontal distance from Alice's town, i.e. by a number between 0 and 1. The joint positions of Alice and Bob at a given instant can therefore be represented by a point $(x
a, x
b)$ in the unit square $[0, 1]\times [0,1]$. The chart giving all ``valid'' joint positions is the set of those points for which the altitudes at points $x
a$ and $x
b$ of the trail are equal. For example, let's construct the chart corresponding to figure (\Figviii):
\numfig 3.7cm{(\Figix)}

As you can see, this chart is almost entirely unidimensional, i.e. consists mostly of linear arcs joined at the vertices. To see why this is so, consider an arbitrary point $p=(x
a, x
b)$ on the chart. This point can be classified in one of four cases according to the slopes of the mountain trail at the positions $x
a$ and $x
b$.

\mfig 4cm
\indent {\it Case 1. Neither of the two positions is at a peak or a valley bottom.} For each position $x
b\pr$ of Bob sufficiently close to $x
b$, there will be only one position $x
a\pr$ of Alice that has the same altitude and is close to $x
a$. Therefore, while Bob and Alice are in some neighborhood of $(x
a, x
b)$, the movements of Alice will be entirely determined by those of Bob. The points of the chart close to $p$ constitute a subset of dimension 1, i.e. a line segment (straight or curved).
\endmfig

\mfig 2.5cm
\indent {\it Case 2. Exactly one of the two positions (say $x
a$) is at a peak or a valley bottom.} The same discussion applies here also, only now Bob may have to back up for Alice to cross her peak or valley. We will consider this point of the chart as being a vertex of degree two.
\endmfig

\mfig 6cm
\indent {\it Case 3. The positions $x
a$ and $x
b$ correspond to two peaks or two valley bottoms.} Bob and Alice can get out of this situation in four possible ways, since each of them can choose freely between moving forwards or backwards. Except at $p$ itself, there will be some neighborhood of  $(x
a, x
b)$ where the movements of Alice determine those of Bob, or vice-versa. The point $p$ is therefore incident to four one-dimensional portions of the chart, i.e. is the meeting point of four edges, and it itself becomes a vertex of the chart.
\endmfig

\mfig 4cm
\indent {\it Case 4. The position $x
a$ corresponds to a peak, and $x
b$ corresponds to the a valley bottom (or vice-versa).} Clearly, if Alice and Bob get into this situation by some miracle, they will be completely unable to move. The point $p$ is therefore an isolated vertex of the chart.
\endmfig

\mfig 6cm
Actually, there are a couple of situations that are not covered by the ones listed above. First, in cases 3 and 4 we implicitly assumed that peaks and valley bottoms are isolated points; if this is not true, i.e., if we allow ``plateaus'' or valleys with flat floors, the arguments used above are no longer valid. If both Alice and Bob are on flat portions of the trail at the same level, then they can move back and forth independently of each other, and still mantain the same altitude. In the chart, this corresponds to a rectangle of nonzero width and height consisting entirely of valid points. Since the arguments become much simpler when the chart contains no subsets of dimension 2, we will assume the trail contains no such flat portions.
\endmfig

The other special cases are the four corners of the chart. It is easy to check that these points are incident to exactly one line of the chart. For example, from the point $(0, 1)$ (the initial situation) Bob and Alice can move only towards each other, which corresponds to moving up and to the left in the chart. So, the chart consists of vertices connected by lines; each line connects two vertices, and each vertex may have degree zero, two or four (except for the corners of the square; they have degree 1).

\mfig 5.2cm
This allows us to prove that Alice and Bob can always meet: If we add two dummy edges connecting the corners $(0,1)$ to $(1, 0)$, and $(0,0)$ to $(1,1)$, the chart becomes an Eulerian graph, which can be decomposed into a collection of cycles so that every edge occurs in only one cycle. In particular, there is a cycle containing the dummy edge from $(0,1)$ to $(1, 0)$, i.e. there is a path on the chart connecting those two vertices. That path must cross the main diagonal at some point $(x, x)$. We can interpret this path as a plan for solving the problem: it tells how Bob and Alice should move from the initial situation so as to come together at position $x$.
\endmfig

What is the relation between this puzzle and the convolution of outlines? What they have in common is the ``matching'' process: we are given two functions $f$ and $g$ of a parameter $t$, and we have to pair up the instants $t$, $t\pr$ where $f(t)=g(t\pr)$. In the Mountaineers' Problem the parameter $t$ is the distance $x$ from Alice's town, and $f$ (which is the same as $g$) gives the altitude at each point. In the convolution of outlines, the parameter $t$ is time; $f$ and $g$ give for each instant the directions in which the cars on the two outlines are facing.

There are a couple of important points to notice in the solution to the Mountaineer's problem. First, the set of all pairs of matching $x$'s ($t$'s) is almost unidimensional, i.e.it may be decomposed into a collection of loops and isolated points. In general, there is no way to traverse one of those loops so that both $t$ and $t\pr$ always increase; indeed, each of those two parameters may be both increasing and decreasing as we move along different parts of the loop. For the Mountaineer's Problem, this implies neither Alice's position not Bob's can be used to measure their joint progress towards the goal. For the convolution of outlines, it means the time to be assigned to a state $a+b$ of the car in $A\ast B$ cannot be a simple function of the time when $a$ was traversed in $A$ and when $b$ was traversed in $B$. As the car traverses a loop of the convolution according to its own clock, the corresponding cars on $A$ and $B$ may have to move ``backwards in time'', retracing their own paths, or stand ``frozen'' (neither moving nor turning); and they may switch from one behavior to the other many times.

The second point is that the number of separate loops on the chart may be greater than one, and indeed the chart may contain disconnected parts. Figure (\Figix) illustrates this situation in the Mountaineer's case, and the example below shows that a similar thing can happen in the convolution of outlines.
\figspace 4cm

As a final remark, notice that the length of the path in the chart can be much longer than the width of the mountain range. A better appreciation of this fact can be obtained from a discrete version of the Mountaineer's problem: consider a mountain range consisting of a polygonal line with $n$ edges, each having equal length and slope $\pm 1$ (i.e., tilted by $\pm45\deg$). Then the vertices of the chart will form a regular grid, and every edge of the chart will connect two opposite corners of a grid cell. Since there are $O(n^2)$ such cells, the shortest solution path will have at most $O(n^2)$ edges. A mountain range that attains this bound is given below:
\figspace 3cm
Clearly, in order for Bob to overcome a peak, Alice has to go all the way from her starting point to the taller peak in the middle. Then she has to go back all the way to the starting point, in order to keep level with Bob while he passes the bottom of the next valley. Note that in this process there are times when both Alice and Bob travel away from their respective goals. They will not be able to meet before traversing $O(n^2)$ edges.

A similar result holds for the convolution: if $A$ and $B$ are two polygonal outlines with a total of $n$ edges, their convolution can have at most $O(n^2)$ edges. The figure below shows an example in which this bound is attained.
\figspace 4cm

The solution we gave for the Mountaineer's Problem implicitly assumes that Bob and Alice have complete knowledge of the topography of the path, so that they can construct the corresponding chart and determine the path from it before starting on their journey. Is there a solution that does not depend on this knowledge, nor on the past history of the trip? In other words, is it possible for Bob and Alice to decide at each instant their next move based only on the local conditions of the trail?

The answer is yes, and it is implied by the following version of Euler's theorem: if in a directed graph every vertex satisfies Kirchoff's law (the number of incoming edges is equal to the number of outgoing ones), then the graph can be decomposed into edge-disjoint directed cycles. Furthermore, if every vertex has exactly one edge coming in and one edge coming out, we can find a cycle containing a given directed edge just by following the arrows blindly until we get back to the same point.

To use this result, we have to assign a direction to each edge of the chart, based on local characteristics of the trail at the current positions of Bob and Alice, in such a way that Kirchoff's law is satisfied. We claim the following set of rules achieves this purpose: at a point $(x
a, x
b)$ on some edge $e$ of the chart,

\item if the slope of the trail at $x
a$ is positive, direct the edge $e$ in the direction of decreasing $x
b$;

\item if the slope of the trail at $x
a$ is negative, direct $e$ towards increasing $x
b$;

It is easy to check that vertices of degree two in the chart (corresponding to Alice being at a peak or valley bottom while Bob is on a slope, or vice versa) have exactly one edge coming in and one coming out. Similarly, wertices of degree four (corresponding to Alice and Bob being simultaneously at two peaks or two valley bottoms) get two edges coming in and two coming out.

To complete the construction, have to pair each edge coming into a node with one that goes out, again based on local information, so that a vertex of degree four behaves like two distinct vertices of degree two. It can be verified that one of the two incoming edges corresponds to Alice and Bob moving in the same direction, and the other to them moving in opposite directions. The same holds for the two outgoing edges. Therefore the two incoming edges are adjacent, and the pairing rule can be stated quite simply:

\item at a vertex of degree four, connect each incoming edge with the outgoing one that is directly opposite to it.

In more intuitive terms, we can state these rules as follows: if Alice is on a slope rising to the right (independently of the way she was moving), then Bob should proceed to the left; if Alice is on a slope that rises to the left, then Bob should retrace his steps by moving right. In both cases, Alice should move as required to keep them at the same level. If Alice is at the bottom of a valley or at a peak, she must continue across it, moving in the same direction she was moving as she got there, and Bob must keep level with her. If Bob too is at a peak or at a valley, he too should preserve his direction of movement.

\mfig 6cm
These rules can also be stated in a reverse form, in which Bob decides how Alice should move, based on the slope at his current position. As one could expect, this requires also reversing the roles of right and left. The nice thing about these rules is that they are symmetric: even if Alice and Bob cannot agree on who leads and who follows, and both try to play the part of the leader, their decisions will always agree.

For example, if Alice and Bob are both on slopes that rise to the right, Alice will conclude that Bob should move left, and Bob will tell Alice to move left --- which is a valid option. As a second example, if Bob is at a slope and Alice is at a peak that she reached by moving to the right, then Bob must have been going up and to the left. Then Alice, following her own set of rules, will proceed to the right and down, past the peak, and will tell Bob to move right. If Bob were the leader, he would tell Alice to move to the right, and in attempting to keep level with her, he would have to move right.
\endmfig

What we need in the convolution problem is exactly a set of ``rules of the road'' like the ones above, that can decide the direction of traversal of $A\ast B$ in a consistent and symmetrical way, based only on local information. Such a set of rules can easily be derived from the ones above by exploiting the analogy between the two problems; the reader can try to derive them as an exercise, but we will not bother to give them until after we have defined formally the concepts of outline and convolution.

\section {9.6. Formal definitions}


\subsection {9.6.1. Oriented lines and ordered spans}

A {\it direction vector in the plane}, or {\it direction} for short, is simply a plane vector of unit length. The {\it circle of directions} $S^1$ is the set of all possible direction vectors, and can be interpreted as (the perimeter of) the unit circle centered at the origin.

In classical geometry, we usually think of a straight line as being just a set of points satisfying some properties or axioms. Under this interpretation, we must perforce conclude that two lines are the same iff they contain exactly the same points. In computational geometry, however, it is in general more convenient to use the concept of an {\it oriented line}, which can be thought of as a classical straight line plus one of the two direction vectors that are parallel to it. This vector is called the {\it orientation} of the line. In this chapter, all lines should be assumed to be oriented unless it is stated otherwise.

\mfig 3cm
We denote by $\di r$ the orientation vector of a line $r$, and we indicate it in figures by a solid arrowhead ($\rpoint$) placed on top of the line. Given two distinct points $a$ and $b$, there are exactly two lines passing through them: one with orientation vector pointing from $a$ towards $b$, and one with the opposite orientation.
\endmfig

If two lines pass through exactly the same set of points, they are either the same line or one is the {\it opposite} of the other. Similarly, if two lines have no points in common, they may be either {\it parallel} (if they have the same orientation vector) or {\it antiparallel} (if their orientations are opposite). The only other possibility, of course, is that the two lines intersect at exactly one point.
\figspace 2.7cm

We define the {\it right} and {\it left sides} of a line $r$ as the half-planes bounded by $r$ and lying respectively to the right and to the left\foot\dag{Strictly speaking, this distinction can only be made once we define ``right'' and ``left'' for the plane, for example by selecting an ordered pair of orthonormal vectors as a prototypical ``right-handed'' coordinate system.} of an observer that stands on $r$ and faces in the direction $\di r$. If $p$ is a point of the plane that is not on $r$, the following expressions are equivalent by definition:

\item {\it $p$ lies on the left side of $r$};

\item {\it $p$ is to the left of $r$};

\item {\it $r$ passes to the right of $p$};

\item {\it $r$ turns left around $p$} (or {\it as seen from $p$}).

In the same way we define the analogous expressions with ``right'' and ``left'' interchanged.

In the rest of this course, we will often have to specify carefully whether a line segment $ab$ is open or closed, i.e. whether it includes or not its endpoints $a$ and $b$. In such occasions, we will use $[a\sp b]$ to denote the closed version.

\mfig 4cm
An {\it arc of directions}, or simply an {\it arc}, is a set of unit vectors that corresponds to a connected proper subset of the unit circle $S^1$. An arc is {\it closed} if it includes both of its extremities, and {\it open} if it includes neither of them. An arc is {\it proper} if it contains no pair of opposite directions, i.e. if it covers strictly less than half of $S^1$. Given two directions $u$ and $v$ that are not opposite to each other, there is exactly one closed proper arc with extremities $u$ and $v$. We will denote such an arc by $[u\sp v]$.
\endmfig

In general, we will use the notation $[a\sp b]$ (the {\it span between $a$ and $b$}) to represent the set that includes $a$, $b$, and all ``things'' of the same sort as $a$ and $b$ that lie ``in between'' the two, whenever this concept has been defined. We will use the notation $(a\sp b)$ for the set $[a\sp b]-\set{a, b}$. Sometimes, we will also use the mixed notations $[a\sp b)$ and $(a\sp b]$, with obvious meaning. So, for example, if $a$ and $b$ are points, $(a\sp b)$ is the open segment $ab$; if $a$ and $b$ are non-opposite directions, $[a\sp b)$ is the proper arc with endpoints $a$ and $b$, including the first but not the second. In general, the elements $a$ and $b$ will be called the {\it extremities} or {\it extremal elements} of $[a\sp b]$ (and also of its open and half-open variants).

Furthermore, we will use the expression $[a\to b]$ to denote the {\it ordered span from $a$ to $b$}: it is the same set as $[a\sp b]$, but ordered according to ``distance'' from $a$ (whenever this concept makes sense). We say that $[a\to b]$ {\it passes through} an element $x$ {\it before} another element $y$ if and only if $x$ is closer to $a$ than $y$ is.

The {\it initial} and {\it final elements} of $[a\to b]$ are respectively $a$ and $b$.  It is sometimes convenient to imagine $[a\to b]$ as a motion or evolution, continuous through time, that goes from object $a$ to object $b$; the nomenclature given above derives from this interpretation. Accordingly, the {\it time reversal} of $[a\to b]$, written $\ne [a\to b]$, is the ordered set $[b\to a]$ that contains the same points but in reversed order. Note that $[a\sp b]$ and $[b\sp a]$ are the same thing, but $[a\to b]$ and $[b\to a]$ are different (unless $a=b$).

\mfig 4cm
If $a$ and $b$ are two points of the plane, $[a\to b]$ then represents the motion from point $a$ to point $b$. If $a$ and $b$ are two non-opposite directions, then $[a\to b]$ can be imagined as the act of rotating a direction vector from $a$ to $b$ along the shortest arc connecting the two; this rotation can be either to the left (counterclockwise) or to the right (clockwise). The open and half-open ordered sets $(a\to b)$, $[a\to b)$, and $(a\to b]$ are defined in a similar way, and all the above definitions and nomenclature are extended to them in the obvious manner.
\endmfig

\subsection {9.6.2. States, moves and turns}

\mfig 4cm
We define a {\it state} $s$ as a pair consisting of a {\it position} $\po s$ (a point of the plane) and an {\it orientation} $\di s$ (a direction vector). This definition is intended as a formal equivalent for the concepts of ``car position'' and ``the way the car is facing'' that we used in the previous sections. The point $\po s$ represents the position of the car at some instant, and $\di s$ shows the direction in which the car was facing at that time. The {\it tangent} to the state $s$ is the oriented line $\ta s$ that passes through $\po s$ and has orientation $\di s$.
\endmfig

If $r$ and $s$ are two states sharing the same tangent line, we define the {\it move from $r$ to $s$} as the ordered set $[r\to s]$ of all states with same orientation as $r$ and $s$ and whose positions traverse the ordered segment $[\po r\to \po s]$. In terms of the car analogy, this corresponds to the car going from $\po r$ to $\po s$ in a straight line, while preserving its orientation. We say that the move $[r\to s]$ with $r\neq s$ is a {\it forward} one if the common tangent is oriented from $\po r$ towards $\po s$, and a {\it backwards} one if it is oriented in the opposite direction.

If $r$ and $s$ are two states with the same position and whose orientations are not opposite to each other, we define the {\it turn from $r$ to $s$} as the ordered set $[r\to s]$ of all states that have the same position as $r$ and $s$ and whose directions traverse the ordered arc $[\di r\to \di s]$. This corresponds to the car changing the way it is facing from $\di s$ to $\di r$ while standing still at the common position $\po r=\po s$. The turn $[r\to s]$, with $r\neq s$, is said to be a {\it left} or a {\it right} turn according to the sense of rotation of the orientation vectors $[\di r\to \di s]$.

In diagrams, a move $[r\to s]$ is indicated by a line segment connecting  $\po r$ to $\po s$, with a solid arrowhead ($\rpoint$) showing the orientation $\di r=\di s$ of the common tangent, and a normal arrowhead ($\scriptstyle >$) pointing from $r$ to $s$ to indicate the direction of movement. A turn $[r\to s]$ is represented by the two intersecting tangents $\ta r$ and $\ta s$ (with solid arrowheads indicating their directions); the direction of turning is indicated by a small bent arrow from $r$ to $s$.
\figspace 3cm

We say that a move or turn $[r\to s]$ {\it traverses}, or {\it passes through}, all positions $[\po r\to\po s]$ and all directions $[\di r\to\di s]$. The {\it time-reversal} of a turn or move $[r\to s]$ produces the turn or move $[s\to r]$ that traverses the same states in the opposite order. Note that the orientation ($\rpoint$) of each intermediate state is not affected, only the direction of motion.
\figspace 3cm

\subsection {9.6.3. Polygonal tracings}

A {\it polygonal tour} with $n$ moves is a cyclic sequence of $2n$ states
$$S=\langle s
0\, s
0\pr\, s
1\, s
1\pr\, s
2\, s
2\pr\, \ldotss\, s
{n-1}\,s
{n-1}\pr\rangle$$
such that, for all $i$, $[s
i\to s
i\pr]$ is a move and $[s
i\pr\to s
{i+1}]$ is a turn; i.e., $\ta s
i=\ta s
i\pr$, $\po s
i\pr = \po s
{i+1}$, and the directions $\di s
i\pr$ and $\di s
{i+1}$ are not opposite. The term ``cyclic'' means that all indices are computed modulo $n$, i.e. $s
{i\pm n}=s
{i}$, $s
{i\pm n}\pr=s
i\pr$ for all integers $i$.

The states $s
i, s
i\pr$, for all $i$, are the {\it critical states} of the tour. The {\it moving states} and the {\it turning states} of $S$ are all non-critical states of its moves and turns, respectively\foot\dag{These collections of states should be interpreted as multisets rather than ordinary sets: the multiplicity of a critical state is the number of times it appears in the sequence $S$, and the multiplicity of a moving or turning state is the number of moves or turns passing through it. For an introduction to the theory of multisets, see for example section 4.6.3 of Knuth's book [\Knu]}. The moving or turning states of a tour are further subdivided into {\it forward} and {\it backward}, or {\it left}, and {\it right}, respectively, depending on the kind of move or turn to which they belong.

In the figures, we will draw the tour $S$ as a polygon whose vertices are $\po s
0, \po s
1, \ldotss, \po s
{n-1}$. The sides of such polygon correspond to moves, and the vertices to turns. We have to indicate only the orientation of each side ($\rpoint$) and the direction of motion of any one of them ($\scriptstyle >$); this information uniquely determines the sequence of critical states, and therefore the tour\foot\ddag{Except in some degenerate cases having superimposed vertices, moves of zero length, etc.}. Furthermore, when some black arrows are omitted, it is implicitly understood that either all moves are forward or all are backward.
\figspace 4cm

Note that the definition of tour given above does not allow the car to turn by $180\deg$ or more in a single turn; one can still get essentially the same effect, however, by a sequence of two or more proper turns separated by moves of zero length.

A {\it polygonal tracing} is a finite multiset $T=\set{T
1, T
2, \ldots, T
m}$ of polygonal tours. The multiset of critical states of $T$ is by extension the (multiset) union of the critical states of its tours. The moves, moving states, turns, and turning states of $T$ are defined in the same way. The {\it critical points} and {\it critical directions} of $T$ are those of its critical states.

\subsection {9.6.4. Winding numbers and degree}

In this section we will define two important numerical properties of a tracing: the winding number function $w(p, T)$, and the degree $\delta(T)$. Besides being interesting concepts by themselves, we will need them to establish the connection between the convolution of tracings and the original brush-and-trajectory metaphor.

Let $T$ be a polygonal tracing, $p$ a point of the plane, and $r$ an oriented line through $p$. Let $r
p$ be the ray of $r$ that has origin $p$ and goes to infinity in the direction pointed to by $\di r$. The {\it crossing number of $r
p$ with respect to $T$} is defined as the number of moves of $T$ that cross $r
p$ from right to left, minus the number of those that cross it from left to right.

\mfig 7cm
\digress{For this definition to make sense, we must define precisely what it means for a move to cross $r
p$. Actually, for the purposes of this chapter, we can be lazy and define the crossing number only for ``clean'' situations, when none of the moves pass through $p$ and the line $r$ contains no critical points. With these conditions, every move that passes through a point of $r
p$ has one endpoint on the left of $r$ and one on the right, so the direction of crossing is unambiguously defined.

\dp However, for the benfit of theorem {\The4} below, and for other purposes unrelated to convolution, it may be more convenient to define this number for all $p$ and $r$. To get a consistent definition, we must count crossings in the following way: if a move $[x\to y]$ of $T$ passes through a point of  $r
p$ other than $p$ itself, count $+{1\over2}, 0$ or $-{1\over2}$ depending on whether $x$ is to the left of $r$, on $r$, or to its right; and then add $+{1\over2}$, $0$ or $-{1\over2}$ depending on whether $y$ is to the right of $r$, on $r$, or to its left. If the move passes through $p$, proceed the same way but add only half of those amounts.

\dp A few checks will show that these rules count ``proper'' crossings as $\pm1$ according to their direction as seen from $r$, and ignore tangency points and moves along the line $r$ or its opposite.}
\endmfig

By considering how crossings and counts change as the line $r$ rotates continuously around $p$, we can easily construct a tedious but straightforward proof of the following result:

\theorem{\The4}{The crossing number of $r
p$ with respect to $T$ is the same for any line $r$ through $p$.}

This number is therefore a property of $p$ and $T$ alone: it is called the {\it winding number of $p$ with respect to $T$}, and is denoted by $w(p, T)$. Intuitively speaking, it counts how many times the tours of $T$ ``wind around'' $p$, where we count each complete circuit as $+1$ if counterclockwise, and $-1$ if clockwise (as seen from $p$). If no move of $T$ passes through $p$, its winding number is a signed integer.

\digress{If a tour passes through $p$, we will for this chapter regard the winding number as undefined. If the more general definition given above is used, then such a turn contributes $\pm{1\over2}$ to the winding number.}

As we did in the informal discussion, we can interpret the function $w$ as a ``figure'' $\T$ of which $T$ is the outline; for example, we can define $\T$ as being the set of all points $p$ for which $w(p, T)$ is nonzero.

Unfortunately, this simple approach will not make theorem {\The3} true. Consider for example the tracing $T$ shown below; according to the definition above, the winding number $w(p, T)$ is one inside the rectangle and zero outside, so the figure $\T$ consists of the interior of the same. Therefore, if we move the square brush $\B$ along $\T$, we should get the fat rectangle (a). Yet, if we compute the convolution $B\ast T$ (according to either the informal discussion, or the rigorous definition below), we will get simply a displaced copy of $T$.
\figspace 3cm

This failure is understandable, since the winding number does not take into account the orientation of the tangents, which are fundamentally relevant for the convolution. So, it is not surprising that the winding numbers of $T$ are insufficient for predicting the results of that operation.

The {\it degree} $\delta(T)$ is simpler than the winding number function, but it is in a sense similar to it. For an arbitrary direction $d$ that is not a critical direction, compute the number of turns of $T$ that pass through $d$, counting each left turn as $+1$ and each right turn as $-1$. Let's call this provisionally the {\it sweeping number of $d$ with respect to $T$}.
\figspace 3cm Then we have the following result:

\theorem{\The5}{The sweeping number of a direction $d$ with respect to a tracing $T$ is the same for all $d$.}

Like in the case of theorem {\The4}, a straightforward proof can be obtained by considering how this number changes (or, rather, doesn't change) as the direction $d$ rotates continuously.

Informally, the degree is the total number of complete turns the car performs on itself when it traverses all the tours of $T$, counting clockwise turns as $-1$ and counterclockwise ones as $+1$. It takes into account the directions and orientations at the turns, but ignores the moves altogether.

\section {9.7. Convolution of tracings}


We will define convolution only for pairs of polygonal tracings that satisfy a ``transversality'' condition, soon to be described. Its analog in the Mountaineer's Problem is the condition excluding mountain ranges with two plateaus (or a plateau and a peak, or a plateau and a valley bottom) at the same height; this restriction is necessary to avoid solid rectangles and vertices of odd degree in the joint position chart. (This chart is the fiber product over the altitude function, for the topologists among you).

We say that two states are {\it parallel} if they have parallel tangents, i.e. the same orientation. Two polygonal tracings $A$ and $B$ are said to be {\it transverse} iff there there is no pair of critical states $a$ from $A$ and $b$ from $B$ that are parallel to each other.

The transversality condition implies in particular that no move of $A$ is parallel to a move of $B$; i.e., in every pair of parallel states $a$ from $A$ and $b$ from $B$, at least one of them is an intermediate turning state. In terms of the car analogy, it means that if a car traversing a loop of $A$ at some instant faces the same way that a car that is traversing $B$, then at least one of them is in the process of turning at a corner while standing still.

To simplify the wording of the convolution procedure, we will define first some auxiliary operations. The {\it sum} $r+s$ of two parallel states $r$ and $s$ is the state having position $\po s+\po r$ and their common orientation. We say that a move $m=[p\to q]$ and a turn $t$ {\it match} iff there is some intermediate state $x$ of $t$ that is parallel to $m$ (i.e., parallel to both $p$ and $q$). In that case, we define the {\it sum} $m+t$ as being either $[p+x\,\to\, q+x]$ or $[q+x\,\to\, p+x]$, depending on whether $t$ turns to the left or to the right.
\figspace 4cm

We say that two turns $t=[r\to s]$ and $t\pr=[r\pr\to s\pr]$ {\it match} iff they have a pair of parallel states, i.e. if the arcs they cover on $S^1$ have a nonempty intersection. In that case, we define their {\it sum} $t+t\pr$ as being the turn whose intermediate states are all sums $x+x\pr$, where $x$ is an intermediate state of $t$ and $x\pr$ a parallel one of $t\pr$. The orientations of these sums will cover the intersection of the two arcs $[\di r\sp\di s]\inte[\di r\pr\sp\di s\pr]$. The sense of rotation of  $t+t\pr$ is by definition counterclockwise if $t$ and $t\pr$ turn the same way, and clockwise if they turn in opposite ways.
\figspace 4cm

If $A$ and $B$ are transverse tracings, we define the {\it convolution graph} of $A$ and $B$ as a directed graph whose vertices are a multiset of states (to be defined later), and whose edges are a multiset of moves and turns, consisting of

\item all moves of the form $m+t$ where $m$ is a move from one tracing and $t$ is a matching turn from the other; and

\item all turns of the form $t+t\pr$ where $t$ is a turn of one tracing and $t\pr$ is a matching turn of the other.

To see the connection between this ``graph'' and the convolution $A\ast B$ of two tracings $A$ and $B$, let's recall what this operation means in terms of the car analogy: we have to match every instantaneous position assumed by a car traversing $A$ with every parallel one of a car traversing $B$; for every such pair, there will be an instant in the traversal of $A\ast B$ where the car will be at the vector sum of the two position and facing in the same direction. This agrees precisely with the definitions of $m+t$ and $t+t\pr$ given above.

The way we determine the ordering of the states $m+t$ and $t+t\pr$ is perhaps less clear. This part of the definitions can be summarized in the following rules, where $t$ is a turn and $z$ is a matching turn or move being added to it:

\item if $t$ turns left, preserve the ordering specified by $z$;

\item if $t$ turns right, reverse the ordering specified by $z$.

The transversality condition ensures that in every pair of matching states at least one of them belongs to a turn, that can be used as the arbiter $t$ of the rules above. These rules are the analog to the ``rules of the road'' of the Mountaineers' Problem, the rules that Alice and Bob should use to decide at every step in which direction they should move. As in the Mountaineer's Problem, these rules are nicely symmetric: when we are adding two turns, it doesn't matter which of the two is used as the ``arbiter'' $t$: in any case, the ordering of the states in the sum will be the same.

The edges of the convolution graph correspond then to the chart of joint positions of Alice and Bob in the Mountaineers' Problem. The figure below illustrates two polygonal tracings and their convolution graph:
\figspace 4cm

Thanks to the transversalty condition, and to the way we defined the sum of moves and turns, it is the case that the extremal states of every turn and move of the convolution graph is of the form $s+x$, where $s$ is a critical state of one tracing and $x$ is a parallel turning state of the other. These states, with their appropriate multiplicities, are the {\it vertices} of the convolution graph. The following is an important property of the convolution graph:

\theorem{\The6}{It is possible to define the incidence relationships of the convolution graph so that every vertex has exactly one incoming move and one outgoing turn, or vice-versa.}
\proof{Let $v=a
1+x$ be a vertex of the graph, where, without loss of generality, we assume  $a
1$ is a critical state of $A$, and $x$ a turning state of $B$. Let $a
0$ and $a
2$ be the two states preceding and following $a
1$ on the tour of $A$ containing it; let $t$ be the turn of $B$ containing $x$. We have four cases to consider:

\mfig 6cm
\pp (a) $t$ turns left, and $m=[a
0\to a
1]$ is a move. Then  $m+t=[a
0+x\,\to\, a
1+x]$, ordered that way, will be a move of the convolution graph. Also, $t\pr=[a
1\to a
2]$ will be a turn of $A$ that matches $t$; the sum $t+t\pr$ will be a turn ordered in the same sense as $t\pr$, and it will have $a
1+x$ for its initial state.

\pp (b) $t$ turns right, and $t\pr=[a
0\to a
1]$ is a turn. Then $m=[a
1\to a
2]$ is a move; the sum $m+t=[a
2+x\,\to\, a
1+x]$, ordered that way, will be a move of the graph with final state $a
1+x$; we make it the only move into $v$. Also, the turn $t\pr$ matches $t$; the sum $t+t\pr$ is a turn ordered in the sense opposite to $t\pr$, and $a
1+x$ will be its initial state.

\pp In both cases, we define $m+t$ is the only move of the graph that comes into (this instance of) the vertex $v$, and $t+t\pr$ the only turn that goes out of $v$.
\endmfig

\mfig 4cm
\pp (c) $t$ is a left turn and $t\pr=[a
0\to a
1]$ is a turn.

\pp (d) $t$ is a right turn and $m=[a
0\to a
1]$ is a move.

\pp For these two cases, the proofs are similar to (a) and (b), except that $m+t$ will be a move going out of the state $a
1+x$, and $t+t\pr$ will be a turn going into it.}
\endmfig

Theorem {\The6} is in a sense the equivalent of the last ``rule of the road'' of the Mountaineers' Problem: it associates to each edge of the convolution graph a unique ``continuation edge'', i.e. it guarantees that every vertex of the graph has indegree one and outdegree one. It is known that such a graph is the union of edge-disjoint closed paths. The vertices of any such path are a sequence of states, alternately connected by moves and turns. This argument allows us to complete the definition of $A\ast B$:

\theorem{\The7}{The convolution graph of two tracings $A$ and $B$ is itself a polygonal tracing $A\ast B$}

In spite of its relative complexity, the definition of $A\ast B$ given above is still far from being ideal. A serious drawback is that the transversality condition is quite strong, and prevents us from, for example, computing the convolution $A\ast A$ of a tracing $A$ with itself, or of two rectangles aligned with the axes.

A practical way to compute the convolution of two tracings that are not transverse, is to ``perturb'' slightly one of them, so that parallel moves cease to be parallel. It is not necessary to actually change the coordinates of the tracing. All it is needed is some consistent criterion for deciding what to do with pairs of parallel moves from $A$ and $B$. A simple example of such a criterion is to always consider the direction of the move from $A$ as being infinitesimally to the left of that of $B$. This destroys the commutativity of convolution, but the differences between $A\ast B$ and $B\ast A$ will not affect winding numbers and degrees, so the two will be essentially equivalent for practical purposes.

A second alternative uses a more esoteric definition of tracing where we essentially identify a number of tracings as equivalent, by omitting the notion of moves. The transversality condition can then be dropped, but on the other hand the definition of winding number and the interpretation of the tracings as figures become somewhat less natural. The research on this topic is still going on, so for these notes we will stick with the definition above.

In a given tracing of size $O(n)$ (the {\it size} of a tracing is the sum of the lengths of its tours), the number of states parallel to any given direction is at most $O(n)$. This implies that the convolution of two tracings of size $O(n)$ is a tracing of size $O(n^2)$. This bound can actually be attained, as shown by the example below. As a matter of fact, even the number of edges bordering the outside infinite region is $O(n^2)$ in this convolution.
\figspace 3cm

The idea of convolution as defined above can be extended to continuous tracings, i.e. tracings whose tours are smooth closed curves, instead of discrete sequences of turns and straight moves. A particular case is that of tracings consisting of turns, straight moves, and moves along arcs of circles; it is easy to check that this family of tracings is closed under convolution. Unfortunately, other interesting families of tracings (for example those allowing conic and parametric cubic spline arcs) are not closed under convolution.

\section {9.8. Other operations on tracings}


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.

\subsection {9.8.1. Affine transformations}

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$.
\figspace 3cm
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$).
\figspace 4cm

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.

We define the image of a state $s$ under a mapping $T$ as the state $s^T$ with position $\po s^T$ and tangent line $(\ta s)^T$.
\figspace 4cm

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\sp q)$ if and only if $x^T$ is in $(p^T\sp q^T)$. Similarly, if the three lines $r, s$ and $t$ are such that $\di t$ is in the proper arc $(\di r\sp \di s)$, then the same relationship holds for their images under $T$.
\figspace 3cm

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.
\figspace 3cm

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.
\figspace 3cm

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}$.
\figspace 4cm

\subsection {9.8.2. Addition and multiplication of tracings}

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.
\figspace 4cm

\vskip 0.5cm plus5cm minus0.5cm

\ctrpar\textwidth pt{\flower\hskip2cm\flower\hskip2cm\flower}

\vskip 0.5cm plus5cm minus0.5cm

If $[u\to v]$ is a move of $A$, we say that the segment $(\po u\to\po v)$ is one of its {\it edges}, and the critical points $\po u, \po 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.
\figspace 3.5cm

\mfig 5cm
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

\mfig 6cm
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.
\figspace 3cm

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 $a
1, a
2$ 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(a
1, B)=w(a
2, B)=w(v, B)$. Then the product tracing will contain that many copies of the turn $t$, each connecting one copy of $a
1$ to one copy of $a
2$. 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.
\figspace 3cm

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 $a
1$ of $A$ and $b
1$ of $B$ coming into any such vertex $x$, and also two edges $a
2$ of $A$ and $b
2$ of $B$ coming out of it. Moreover, the edges $a
1$ and $a
2$ will lie on opposite sides of $b
1$ and $b
2$, and vice-versa. To simplify the discussion, let's rotate the plane so that $a
1$ and $a
2$ are going ``north''; then both $b
1$ and $b
2$ are going in the general ``east'' direction, or both are going ``west'':
\figspace 3cm

\mfig 5cm
In the first case, the winding numbers with respect to $B$ are one higher in the north side of $b
1$ and $b
2$ 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 $a
1$ and $a
2$ 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).

\mfig 3cm
\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.
\figspace 4cm

Before discussing how to extend this procedure for the general case, let's prove that it does what it was supposed to do; namely,

\theorem{\The8}{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
\figspace 3cm
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:
\numfig 3cm{(\Figvii)}

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)$.

\mfig 4cm
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 $A
1$ and $A
2$ 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 $(A
1\cdot B) + (A
2\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 $(A
1\cdot B) + (A
2\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.
\figspace 3cm

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

\subsection {9.8.3. Multiplication - the general case}

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)=w
B+\beta/2$ and $w(b, A)=w
A+\alpha/2$, where $w
A$ and $w
B$ 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 (w
B+\beta/2) + \beta(w
A+\alpha/2)=\alpha w
B+ \beta w
A+ \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 {\The8} to accomodate this special case.
\figspace 3cm

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 $a
1$ and $a
2$ 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 $a
1a
2$ to the other. Each of these crossing will ultimately contribute one unpaired copy of $a
1$ (or $a
2$) to the product tracing. On the other hand, because of $a
1a
2$ the winding numbers with respect to $A$ will be one greater on the left side of $a
1a
2$; 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.
\figspace 4cm

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.

\section{9.9. The meaning of convolution}


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.

\subsection {9.9.1. Convolution of figures}

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 $\B$ along a trajectory $\T$ was to blacken all points of the form $a+b$, where $a\in \T$ and $b\in \B$. There is another interesting way to look at this result:

\lemma{\The9}{The brush $\B$ covers a point $p$ when placed at $a$ if and only if the rotated brush $\B^{-I}$ covers $a$ when placed at $p$.
\figspace 3cm}

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:

\theorem{\The{10}}{The point $p$ is in $\T\oplus \B$ if and only if $\T\inte\B^{p\,-I}\neq \empty$.}

For example, consider the sets $\T$ and $\B$ in the figure below. After a little thinking, it should become clear why theorem {\The{10}} is true.
\figspace 4cm

The interpretation of $A\ast B$ we are going to give next will be basically an extension of theorem {\The{10}} 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 ``$\T\inte\B^{p\,-I}\neq\empty$'' 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.
\numfig 4cm{(\Figviii)}

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 {\The{10}}; 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$:
\figspace 4cm

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.

\subsection {9.9.2. The fundamental theorem of convolution}

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 {\The{10}} in the language of polygonal tracings:

\theorem{{\The{11}} {\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 $\po a= x= p-\po b$, i.e. $p=\po a+\po 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.
\figspace 3cm

Note also the formal analogy of this result with the definition of the convolution of sequences: the
convolution $\langle c
n\rangle$ of $\langle p
n\rangle$ and $\langle p
n\rangle$ is defined by the equation $c
n = \sum
k p
n 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$.
\figspace 4cm

\mfig 4cm
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

\mfig 4cm
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

\mfig 4cm 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 $A
1$ and $A
2$ with identical dimensions and positions but oriented and traversed in opposite directions. In computing $A\ast B$, it is best to use distributivity, computing $A
1\ast B$ and $A
2\ast B$ and then add the results.
\figspace 4cm

\mfig 4cm
The convolution $A
1\ast B$ is not much different from the previous example: the result is a square with rounded corners. The convolution with the clockwise square $A
2$ 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

\mfig 4cm
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 $A
2\ast B$.
\endmfig

\mfig 6cm
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 $A
2\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

\mfig 5cm
The most complex situation that shown here, in which the circle $B^{p-I}$ cuts off two consecutive sides of $A
2$, but misses the corner. Study the illustration shown carefully. First check that the winding number $w(p, A
2\ast  B)$ is 1. Next, check the directions of motion, orientations and turns shown for the product $A
2\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

As our final example, let's consider the same circular brush $B$ convolved with the curved open path $A$ shown below. The convolution is a ``sausage'' envolving the path.
\figspace 3cm

\mfig 6cm
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

\mfig 4cm
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

\par\vfill\eject\end


��X�J�J�<�J��J�?J��
J�YJ�����J��J��J��J��J��J��J��
J��J��J����� �J��J��J�^J��
J��
J��
J��J��J��J��J��J��J�w���6�J��J��J��J��J��J��J��J��J��J��J��J��J�����1�J��J��J��J��J��
J��J��J��J��J��J��J��J��J��J��
J��J��J��J��J��J��J��J�����*�J��J��J��J�5J��J��J��J��J��J��J��J��J��J��J��J��J��J��J��
J��J��J��J�pJ�[J��J��J�tJ��J��J��J�����#J��6J��J��J��J��J��J�.J�'J�,J�CJ�^J��
J��J��J��J��J����-J��J��J��J��J����(J��J��J��J��
J����0J��J��J��J��J��
J��
J�lJ��J��
J��
J��J��J��J�oJ��
J�����(�J��J��J��J��J��J��
J�vJ�tJ��J��
J�AJ�AJ��J��
J��J��J��J��J��
J�HJ�<J��
J��J�kJ��J��J��J��J�����-�J����,J��J��
J��J��J��J��J��J��J��
J��J��
J��J��J��J����=J��J��J��J��
J� J�>J� J��J��J��J��J��J��J��J��J��J��J��
J��
J��J��J��J��J��J��J��J��J��J��J��J����7J��J��J��J��J��J��J�����*�J����,J��J��
J��
J�eJ��
J��J��J��J����<J��J��
J��J��J��
J��J��J��J��J��J��J��J��J��J��
J��J����J�J�����B
��