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

Encouraged by the successes obtained so far, let’s now test theorem \Theiii 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 $\B\oplus\T$ is a square with side $2(L+r)$ and rounded corners.\figno(\Figiv)3

\mfig4
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

\mfig6
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\footfig1(3){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 $t$ of $T$, say the upper left one, then the tangents at that vertex are all the lines through $t$ that point in the generic ``southwest’’ direction. So, $t$ 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 $\B\oplus\T$. A similar thing happens at the other three corners of $T$; the convolution then becomes a closed curve, oriented counterclockwise, which is precisely the outline of $\B\oplus\T$.

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 $\T$ of side $2L$ with {\it empty} interior. We want the resulting figure $\B\oplus\T$ look as shown below: the same rounded square of example \Figiv, but with a square hole of side $2(L-r)$ at is center.\figno(\Figv)4

The outline of $\T$ 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.

\mfig5
What is disconcerting about this curve is that the ``direction of traversal’’ that we get at each point $b+t$ by simply copying the direction of the tangents at $b$ and $t$ 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

\mfig4
Clearly, we can’t assign to $b+t$ the same direction of traversal of $b$ and $t$; 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$.\fig4 Indeed, by formula (1) we see that $\B\oplus(\B\oplus\T)=(\B\oplus\B)\oplus\T$, i.e. the result is the same as that of moving a circular brush $\B\oplus\B$ of radius $2r$ along the square trajectory $\T$. However, the outline $B\ast(B\ast T)$ comes out quite different from $(B\ast B)\ast T$:\fig4

In fixing the direction of traversal of $B\ast T$ 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 $B\ast T$, that cusp will be matched with a whole half-circle of $B$, and will give rise to a similar half-circle segment in $B\ast(B\ast T)$ 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.

As we see, orientations work best if the tangents in the obnoxious arcs of $B\ast T$ 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.

\mfig5
For example, a valid traversal of the the inner perimeter of $B\ast T$ 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 $B$ and $T$, we match all instantaneous positions of the car traversing $B$ with those of the car traversing $T$ 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 ($\lpike$) 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 $B\ast T$ 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 ($\lpike$) 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 $B$ and $T$ 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 $B$ and $T$, and retaining their orientations.

\mfig5
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 $(b, t)$ and $(b\pr, t\pr)$, where $b$ and $b\pr$, as well as $t$ and $t\pr$, were infinitesimally close in time in the their respective outlines. How should the car move in the convolution: from $b+t$ to $b\pr+t\pr$, or vice-versa?
\endmfig

Note that the directions of motion or turning at $b$ and $t$ may not agree: it may be the case that the state $b$ precedes $b\pr$ in time, but $t$ follows $t\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 $B\ast T$, 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 $b+t$ and $b\pr+t\pr$ to be on the same loop of $B\ast T$? Indeed, why do we expect $B\ast T$ 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.

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.\figno(\Figviii)3

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.

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 $(xǎ, xb̌)$ 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 $xǎ$ and $xb̌$ of the trail are equal. For example, let’s construct the chart corresponding to figure (\Figviii):\figno(\Figix){3.7}

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=(xǎ, xb̌)$ on the chart. This point can be classified in one of four cases according to the slopes of the mountain trail at the positions $xǎ$ and $xb̌$.

\mfig4
\indent {\it Case 1. Neither of the two positions is at a peak or a valley bottom.} For each position $xb̌\pr$ of Bob sufficiently close to $xb̌$, there will be only one position $xǎ\pr$ of Alice that has the same altitude and is close to $xǎ$. Therefore, while Bob and Alice are in some neighborhood of $(xǎ, xb̌)$, 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.5}
\indent {\it Case 2. Exactly one of the two positions (say $xǎ$) 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

\mfig6
\indent {\it Case 3. The positions $xǎ$ and $xb̌$ 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 $(xǎ, xb̌)$ 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

\mfig4
\indent {\it Case 4. The position $xǎ$ corresponds to a peak, and $xb̌$ 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

\mfig6
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.2}
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 $b+t$ of the car in $B\ast T$ cannot be a simple function of the time when $b$ was traversed in $B$ and when $t$ was traversed in $T$. As the car traverses a loop of the convolution according to its own clock, the corresponding cars on $B$ and $T$ 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.\fig4

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:\fig3 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.

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 $(xǎ, xb̌)$ on some edge $e$ of the chart,

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:

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.

\mfig6
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 $B\ast T$ 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.