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

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.

\mfig3
We denote by $\stdir r$ the orientation vector of a line $r$, and we indicate it in figures by a solid arrowhead ($\rpike$) 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.\fig{2.7}

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 $\stdir r$. If $p$ is a point of the plane that is not on $r$, the following expressions are equivalent by definition:

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\span b]$ to denote the closed version.

\mfig4
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\span v]$.
\endmfig

In general, we will use the notation $[a\span 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\span b)$ for the set $[a\span b]-\set{a, b}$. Sometimes, we will also use the mixed notations $[a\span b)$ and $(a\span b]$, with obvious meaning. So, for example, if $a$ and $b$ are points, $(a\span b)$ is the open segment $ab$; if $a$ and $b$ are non-opposite directions, $[a\span 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\span 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\span 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 $\timrev [a\to b]$, is the ordered set $[b\to a]$ that contains the same points but in reversed order. Note that $[a\span b]$ and $[b\span a]$ are the same thing, but $[a\to b]$ and $[b\to a]$ are different (unless $a=b$).

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

\mfig4
We define a {\it state} $s$ as a pair consisting of a {\it position} $\stpos s$ (a point of the plane) and an {\it orientation} $\stdir 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 $\stpos s$ represents the position of the car at some instant, and $\stdir s$ shows the direction in which the car was facing at that time. The {\it tangent} to the state $s$ is the oriented line $\sttan s$ that passes through $\stpos s$ and has orientation $\stdir 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 $[\stpos r\to \stpos s]$. In terms of the car analogy, this corresponds to the car going from $\stpos r$ to $\stpos 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 $\stpos r$ towards $\stpos 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 $[\stdir r\to \stdir s]$. This corresponds to the car changing the way it is facing from $\stdir s$ to $\stdir r$ while standing still at the common position $\stpos r=\stpos 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 $[\stdir r\to \stdir s]$.

In diagrams, a move $[r\to s]$ is indicated by a line segment connecting $\stpos r$ to $\stpos s$, with a solid arrowhead ($\rpike$) showing the orientation $\stdir r=\stdir 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 $\sttan r$ and $\sttan s$ (with solid arrowheads indicating their directions); the direction of turning is indicated by a small bent arrow from $r$ to $s$.
\fig3

We say that a move or turn $[r\to s]$ {\it traverses}, or {\it passes through}, all positions $[\stpos r\to\stpos s]$ and all directions $[\stdir r\to\stdir 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 ($\rpike$) of each intermediate state is not affected, only the direction of motion.\fig3

A {\it polygonal tour} with $n$ moves is a cyclic sequence of $2n$ states
$$S=\langle s0̌\, s0̌\pr\, s1̌\, s1̌\pr\, s2̌\, s2̌\pr\, \ldotss\, s{̌n-1}\,s{̌n-1}\pr\rangle$$
such that, for all $i$, $[sǐ\to sǐ\pr]$ is a move and $[sǐ\pr\to s{̌i+1}]$ is a turn; i.e., $\sttan sǐ=\sttan sǐ\pr$, $\stpos sǐ\pr = \stpos s{̌i+1}$, and the directions $\stdir sǐ\pr$ and $\stdir 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=sǐ\pr$ for all integers $i$.

The states $sǐ, sǐ\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 $\stpos s0̌, \stpos s1̌, \ldotss, \stpos 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 ($\rpike$) 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.\fig4

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{T1̌, T2̌, \ldots, Tm̌}$ 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.

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 $rp̌$ be the ray of $r$ that has origin $p$ and goes to infinity in the direction pointed to by $\stdir r$. The {\it crossing number of $rp̌$ with respect to $T$} is defined as the number of moves of $T$ that cross $rp̌$ from right to left, minus the number of those that cross it from left to right.

\mfig7
\digress{For this definition to make sense, we must define precisely what it means for a move to cross $rp̌$. 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 $rp̌$ 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 {\Theiv} 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 $rp̌$ 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:

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 {\Theiii} 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$. \fig3

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$}.\fig3 Then we have the following result:

Like in the case of theorem {\Theiv}, 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.

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 $\stpos s+\stpos 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.\fig4

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 $[\stdir r\span\stdir s]\inte[\stdir r\pr\span\stdir 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.\fig4

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

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:

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:\fig4

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{\Thevi}{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=a1̌+x$ be a vertex of the graph, where, without loss of generality, we assume $a1̌$ is a critical state of $A$, and $x$ a turning state of $B$. Let $a0̌$ and $a2̌$ be the two states preceding and following $a1̌$ on the tour of $A$ containing it; let $t$ be the turn of $B$ containing $x$. We have four cases to consider:

\mfig6
\pp (a) $t$ turns left, and $m=[a0̌\to a1̌]$ is a move. Then $m+t=[a0̌+x\,\to\, a1̌+x]$, ordered that way, will be a move of the convolution graph. Also, $t\pr=[a1̌\to a2̌]$ 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 $a1̌+x$ for its initial state.

\pp (b) $t$ turns right, and $t\pr=[a0̌\to a1̌]$ is a turn. Then $m=[a1̌\to a2̌]$ is a move; the sum $m+t=[a2̌+x\,\to\, a1̌+x]$, ordered that way, will be a move of the graph with final state $a1̌+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 $a1̌+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

\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 $a1̌+x$, and $t+t\pr$ will be a turn going into it.}
\endmfig

Theorem {\Thevi} 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$:

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

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.