\section {9.8. Other operations on tracings}
\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 $a1, a2$ be the moves preceding and following it in $A$. Because of our simplifying assumptions, the vertex $v$ of $t$ is not on $B$, and we have $w(a1, B)=w(a2, B)=w(v, B)$. Then the product tracing will contain that many copies of the turn $t$, each connecting one copy of $a1$ to one copy of $a2$. As in the case of moves, if $w(v, B)$ is negative we take $\leftv w(v, B)\rightv$ copies of the time reversal of $t$. The same rule applies with $A$ and $B$ interchanged.
\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 $a1$ of $A$ and $b1$ of $B$ coming into any such vertex $x$, and also two edges $a2$ of $A$ and $b2$ of $B$ coming out of it. Moreover, the edges $a1$ and $a2$ will lie on opposite sides of $b1$ and $b2$, and vice-versa. To simplify the discussion, let's rotate the plane so that $a1$ and $a2$ are going ``north''; then both $b1$ and $b2$ are going in the general ``east'' direction, or both are going ``west'':
\figspace 3cm
\mfig 5cm
In the first case, the winding numbers with respect to $B$ are one higher in the north side of $b1$ and $b2$ than on the south; the situation is reversed in the second case. In either case, the winding numbers with respect to $A$ are one higher on the western side of $a1$ and $a2$ than on the eastern side. The reader can check that, independently of whether the winding numbers are positive or negative, the situation at $x$ in the product will be essentially the same in all cases: one tracing contributes $p+1$ moves coming into $x$ and $p$ going out of $x$, while the other tracing contributes $q$ incoming moves and $q+1$ outgoing ones.
\endmfig
By definition, the turns of $A\cdot B$ at $x$ will be: $p+q$ ``ordinary'' turns of zero degrees, connecting every incoming move except one to an outgoing move ``straight ahead'' of it; and an ``extraordinary'' turn connecting the unpaired incoming move to its outgoing counterpart from the other tracing. The two unpaired moves, and the extraordinary turn connecting them, are adjacent to the quadrant where the winding numbers are highest for both tracings (and for the product).
\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 $A1$ and $A2$ with opposite orientations. If we multiply each separately by $B$, and add the results, we get the tracing shown at right.
\endmfig
Note that all moves and parts of moves that we got in $(A1\cdot B) + (A2\cdot B)$ but not in $A\cdot B$ are present in two copies, having same orientation but opposite direction of traversal. In the computation of winding numbers, these paired moves always cancel each other, except for points lying on top of them. Similarly, whenever we get an extra turn in $(A1\cdot B) + (A2\cdot B)$ we also get its time reversal, and they cancel each other in the computation of the degree.
To get a cleaner theory of tracings and convolutions, it seems we should consider those two tracings as equivalent, i.e. ignore differences that result from adding or removing an edge (or turn) together with its time reversal. Adding or deleting such ``null'' pairs to a tracing $A$ affects its convolution $A\ast B$ only by the addition or deletion of other null pairs.
Note that two moves passing through the same set of points only cancel each other in this way if they have the same orientation and opposite directions of traversal, as in the first pair of the figure below. The other three pairs shown are {\it not} irrelevant: they affect the winding numbers of whole regions and/or the degree of the tracing.
\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)=wB+\beta/2$ and $w(b, A)=wA+\alpha/2$, where $wA$ and $wB$ are the winding numbers with respect to $A$ and $B$ of a point $y$ just ``east'' of both edges. The product tracing then will contain $\alpha (wB+\beta/2) + \beta(wA+\alpha/2)=\alpha wB+ \beta wA+ \alpha \beta$ copies of the move $a$. (If the edge $b$ moves in the direction opposite to that of $a$, we take $\beta$ to be negative). A little thought shows how to extend the proof of theorem {\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 $a1$ and $a2$ of $A$, say, their winding numbers with respect to $B$ may differ by more than one; this difference corresponds to the net number of times that $B$ crosses $x$ from one side of $a1a2$ to the other. Each of these crossing will ultimately contribute one unpaired copy of $a1$ (or $a2$) to the product tracing. On the other hand, because of $a1a2$ the winding numbers with respect to $A$ will be one greater on the left side of $a1a2$; 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.