\title{Kinetic Framework Extras\cp III. Old Stuff}

\author{J. Stolfi}

}

\note{These comments were written around May 1, 1983, during the preparation of the first version of the Kinetic Framework extended abstract (submitted to FOCS '83}

The convolution of two subsets $A$ and $B$ of the Cartesian plane $\reals^2$ is defined as
$$A\ast B=\rset{a+b\relv a\in A \and b\in B}.\eqno(1)$$
See figure \Fig1.
\capfig 4cm{\hfil Figure 1.}

The convolution can be interpreted in many other ways: for example, if we denote by $B^a$ the set $B$ translated by the vector $a$, then clearly
$$A\ast B=\union
{a\in A} B^a,\eqno(\Eq2)$$
i.e. the union of copies of $B$ translated by every element of $A$. Equation (\Eq2) can be rewritten as
$$x\in A\ast B \rmiff (\exists y\in \reals^2) y\in A \and x-y\in B, \eqno(\Eq3)$$
or, if $f
X$ denotes the characteristic predicate of the set $X$,
$$f
{A\ast B}(x)=\join
{y\in \reals^2} f
A(y)\and f
B(x-y).\eqno(\Eq4)$$
The similarity of this last expression with the classical convolution of two real-valued functions $f$ and $g$, namely
$$f\ast g(x)=\int
{\reals^2} f(y)g(y-x) dy,$$
justifies the name given to the operation $A\ast B$.

Another important characterization of $A\ast B$ is given by the following result. Let $A^{-I}$ be the set $A$ rotated $180\deg$ around the origin, i.e. $ A^{-I}=\rset{-a\relv a\in A}$. Then from equation (\Eq3) we get
$$x\in A\ast B \rmiff A\inte (B^{-I})^x \neq \empty\eqno(\Eq5).$$
That is, the point $x$ is in $A\ast B$ if and only if the set $B$ rotated $180\deg$ and translated by $x$ intersects $A$ (fig. \Fig2).\figspace 4cm

We will see later on that, like its classical counterpart, the convolution defined above is a concept of fundamental importance in computational geometry, and extremely useful in the development of geometrical algorithms.

The {\it outline representation} is one of the simplest and most common ways of describing subsets of the plane. In this model, a figure $A$ is specified by giving a suitable representation of its boundary, which is assumed to be one-dimensional and easier to describe than $A$ itself. For example, a simple polygon $P$ is usually represented by a list of its vertices, with the understanding that the edges of $P$ are the segments connecting consecutive vertices. The boundary can also be described by an algebraic or parametric curve, or by a collection of such curves.

In view of the wide applicability of this model, it is quite natural to consider the problem of computing the outline of $A\ast B$ from the outlines of $A$ and $B$. It is not hard to see that a point $x$ on the boundary of $A\ast B$ must be the sum of a boundary point $a$ of $A$ with a boundary point $b$ of $B$. But the crucual observation is that {\it the tangents to $A$, $B$ and $A\ast B$ at the points $a$, $b$ and $x=a+b$, respectively, must be parallel to each other.}
\figspace 4cm

Why this must be so is clear from figure \Fig3. Imagine that $a$ and $b$ move back and forth along the respective boundaries by an infinitesimal amount: if the tangents at those points were not parallel, the sum $a+b$ would completely cover a parallelogram enclosing the point $x$, contradicting the assumption that $x$ is on the boundary.

We will develop from these observations an algorithm for computing the outline of $A\ast B$ from those of $A$ and $B$: the basic idea is to take all points of the form $a+b$ where $a$ and $b$ lie on the given outlines and have parallel tangents. Unfortunately, this simplistic approach suffers from three major problems

The first problem is that not all points of an outline have a well-defined tangent line. Consider the example of figure \Fig4 {\bf square convolved with circle}.\figspace 3cm The point $x
1$ on the boundary of the convolution has a unique decomposition as $a
1+b
1$ with $a
1\in A$ and $b
1\in B$, but the tangent to $A$ at $a
1$ is not defined. In this particular case, we can preserve the validity of the basic idea by adopting the convention that all lines passing through $a
1$ and sloping down to the right are tangents to $A$. Unfortunately, a general rule of this kind that would work in all cases (including concave corners and cusps) is by no means obvious.

The second problem comes from an inherent ambiguity in the slope of tangent lines, that is also illustrated by the example of figure \Fig4. The tangents to $B$ at the points $b
2$ and $b
2\pr$ have the same slope, which also matches that of the tangent to $A$ at $a
2$. Yet, while $x
2=a
2+b
2$ is a boundary point of $A\ast B$, the point $x
2\pr=a
2+b
2\pr$ is not. We can explain this failure by noticing that the tangents at $a
2$ and $b
2$ touch $A$ and $B$ respectively from above, while the tangent at $b
2\pr$ touches $B$ from below. A possible solution is to orient every tangent line so that the figure interior lies to its left (in the neighborhood of the tangency point), and consider only those pairs of boundary points of $A$ and $B$ where the tangents agree in slope {\em and orientation}. This solution too has problems in coping with concave corners, cusps and other pathological cases.

The third problem is that the equality of slopes at $a$ and $b$ is only a {\em necessary} condition (but not a sufficient one) for $a+b$ to lie on the boundary of $A\ast B$. The converse may fail because the point $a+b$ may also be expressible as $a\pr+b\pr$ for two points $a\pr$ of $A$ and $b\pr$ of $B$ which do not satisfy the basic conditions; an example of this situation is llustratd in figure \Fig5.\figspace 4cm
Stated in another way, the outlines obtained by a straightforward application of the basic rule may be self-intersecting, and therefore some portions of them may be spurious, and lie in the interior of the convolution. This problem is more ``global'' in nature than the previous two: the detection and removal of those spurious portions seems to require a nontrivial processing of the resulting outline.

In the following sections we will discuss a generalized outline representation, based on the concept of {\it tracings}, which solves these problems in a mathematically clean way. The first two problems are solved by requiring the oriented tangent(s) at each point to be explicitly given as an integral part of the outline representation. The last problem is solved by extending the concepts of boundary and interior so as to accept self-intersecting outlines and interpret them in a way that is compatible with the classical one. With these extensions, the basic rule becomes both necessary and sufficient.

The discussion above summarizes the historical motivation for the concept of tracings as defined below. However, the ability to cleanly support the operation of convolution is only one of the reasons that make such objects worth of further study. Another serentipitous but important property is the duality principle discussed in section \Sec5, which is extremely valuable in the synthesis, description and verification of geometrical algorithms.

A convenient and frequently used method to describe a curve is by a {\it parametric representation\/}, in which the curve is visualized as the set of points visited by a pointlike particle as it describes a specified motion through time. In this section we are going to develop a formalism (and an intuitive interpretation) for the parametric representation of generalized outlines.

In this model, a tracing is described intuitively by a car trip on the plane. At any given instant during the trip the car has a definite {\it position} (a point of the plane) and a definite {\it orientation} (the direction towards which the car is facing). This pair of attributes constitutes the instantaneous {\it state} of the car. The {\em oriented} line passing through the position of the car and parallel to its orientation is the {\it tangent} corresponding to the current state of the car. If $s$ is a state, we denote its position by $\po s$, its orientation by $\di s$, and its tangent by $\ta s$. The set of all possible states, that is, all possible pairs of a point and a direction, will be denoted by $W$.

Formally, we can view a car trip as a function $s(t)$ from some time interval $I$ into $W$. Only {\it closed} car trips (in which the initial and final states are the same) will be relevant to this paper; therefore, we will identify the two endpoints of $I$, making it homeomorphic to the unit circle.

To represent a valid car trip, the function $s(t)$ must satify also another couple of conditions. The functions $\po s(t)$ and $\di s(t)$ must be continuous and differentiable (at least to first order), and, the instantaneous velocity of the car ${d\over {dt}}\po s(t)$ must be a real multiple of its instantaneous orientation $\di s(t)$. Intuitively, this means the car moves smoothly, and always along its instantaneous tangent (without skidding). A function with the above properties is called a {\it tour}.

In summary, at each instant during a trip the car may be moving along its current tangent (either forwards of backwards) or standing still. In either of these cases, the car may also be turning (right or left), or keeping its direction fixed. Note that the position and orientation of the car need not be differentable functions of the path length, since their derivatives with respect to time may be zero independently of each other. This allows the path to have corners and discontinuities in curvature.

We can break the interval $I$ into a sequence of open intervals separated by isolated instants, in such a way that (i) no state is encountered twice during an interval\foot\dag{\bf bug with pauses!}\foot\ddag{\bf bug: should also exclude arcs and turns (and moves in tsp) that end and begin on the same state}, and (ii) throughout each interval both the sense of motion (forward, backwards, or stationary) and the sense of turning (left, right, or straight) remain constant. We call each of those intervals a {\it leg} of the trip. Depending on the combination of these attributes, we can classify each leg into one of the following categories:

\item a {\it pause}, if the car neither moves nor turns during the whole interval;

\item a {\it move}, if the car is moving in a straight line (either always forwards or always backwards);

\item a {\it turn}, if the car is turning (either right or left) while stationary;

\item an {\it arc}, if the car is simultaneously moving (either forwards or backwards) and turning (either left or right).\foot\dollar{\bf ugly: the only use for arcs is to say they are forbidden. Convolution of arcs seems to require higher-order states.}

Figure \Fig6 illustrates these categories. The solid arrowhed ($\rpoint$) indicates the orientation of the car, and the normal arrowhead ($\scriptstyle >$) shows the sense of motion.\figspace 5cm

The instant between two consecutive legs is called a {\it critical instant}. In this paper we will restrict our attention to {\it finite polygonal tours}, which have no arcs and only a finite number of other legs.

We may view a tracing as an abstract description of a car trip, a description that seeks to preserve the geometrical and topological features of the trip while omitting practically all timing information. In this paper we will restrict our attention to tours that are both {\it finite} (have only a finite number of legs) and {\it polygonal} (contain no arcs). The tracing determined by such a tour is essentially a count of how many times the car passed through each state of $W$, plus a limited amount of information on how the car was moving and turning on those times. Just as a curve may be parametrized in infinitely many distinct ways, it is possible for many distinct tours to describe the same tracing.

A tracing $T$ is characterized by two integer functions, the {\it moving count} $\mu
T$ and the {\it turning count} $\tau
T$, defined on the set $W$ of all possible states\foot\dag{We will omit the subscript $T$ when implied by context.}. These functions are derived from the corresponding tour as follows: the value of $\mu(s)$ is the number of times the car passed through the state $s$ while moving forward, minus the number of times it passed through $s$ while moving backwards. Similarly, the value of $\tau(s)$ is the number of times the car passed through $s$ while turning, each time counted as $+1$ if the car was turning left and as $-1$ if turning right at that instant. Two functions $\mu$ and $\tau$ from $W$ into $\integers$ constitute a tracing if and only if they are obtained from some tour by the above rules.

The counting of stationary instants (when the derivatives of position and/or direction are zero) requires some extra care. If at some time $t$ the car passes through a state $s$, and there is some neighborhood of $t$ during which the position of the car is constant (i.e., the car is in the middle of a turn or pause), then the car is not considered to be moving, and that occurence of $s$ does not contribute to the $\mu$ count. However, if $t$ is an instant of transition between two moving regimes, that occurence of $s$ contributes to $\mu$ the average mean of the counts corresponding to those two regimes. For example, if the car was moving forward just before $t$, and is stationary for some nonzero interval just after $t$, then that occurence contributes ${1\over2}(1+0)={1\over 2}$ to $\mu(s)$.

In the same way, if the direction of the car was constant troughout some neighborhood of $t$ (i.e., the car is in the middle of a move or pause), the car is not considered to be turning at $t$, and its current state $s$ is not counted by $\tau$. However, if $t$ is the transition between two turning regimes, that occurence of $s$ contributes to $\tau(s)$ the average of the corresponding counts. So, if the car was turning right just before $t$, and was moving straight just after $t$, that occurence of $s$ is counted as ${1\over2}(-1+0)=-{1\over2}$.

Another way of stating these rules is based on a decomposition of the tour into legs. We first define the counting functions $\mu$ and $\tau$ for an isolated leg $e$ in the following way: if $s$ is a a state traversed during $e$, then the pair $[\mu
e(s), \tau
e(s)]$ is $[1,0]$ in the case of a forward move, $[-1,0]$ for a backwards move, $[0,1]$ for a left turn, $[0,-1]$ for a right turn, and $[0,0]$ for a pause.\foot\dag{\bf bug: requires all states in a leg (including the endstates) to be distinct. If we accept arcs this may be a bad idea, but doesn't seem likely.}. If $s$ is the initial or final state of $e$, $\mu
e(s)$ and $\tau
e(s)$ are half those amounts. For all other states, $\mu
e$ and $\tau
e$ are zero. The counting functions $\mu
T(s)$ and $\tau
T(s)$ of the tracing $T$ are then the sum of $\mu
e(s)$ and $\tau
e(s)$, respectively, for all legs $e$ of the tour.

Clearly, the speed with which the car covered each leg of a tour does not affect the corresponding tracing. Note also that a pause and its two adjacent critical instants can always be contracted to a single critical instant without changing the values of $\mu$ and $\tau$ of any state. The tracing is also unaffected by spurious stops: for example, if the car moves forward in a straight line, comes to a stop in a state $s$, and then accelerates straight forwards again, the state $s$ is counted as $\mu={1\over 2}+{1\over2}=1$ and $\tau=0+0=0$, exactly as if the car had moved through $s$ at constant speed.

Notice that the functions $\mu$ and $\tau$ do not depend on the order in which the legs occur, but only on how many times each is traversed. Therefore, the definition of $\mu$ and $\tau$ given above can be applied to an arbitrary multiset of moves and turns \foot\ddag{\bf and pauses, for those wo like them}, even if they cannot be connected to each other to form a valid tour. Such an object will be called a {\it partial tour}, and the corresponding counting functions define a {\it partial tracing}.

Note in addition that two legs of a tour that cover the same states in opposite order (for example, a forward and a backward move along the same line segment) effectively cancel each other in the computation of $\mu$ and $\tau$. We can therefore look at a backward move with multiplicity $k$ as being the corresponding forward move with multiplicity $-k$, and redefine partial tours as signed multisets of forward moves and left turns only. If $T$ is such a partial tour, we denote by $\kappa
T(e)$ the multiplicity of a given leg $e$ in $T$.

To check whether a partial tour (given as a multiset of legs) is a closed one, we define the ``free valence'' counting function $\nu(s)$ as follows: if $e$ is a forward move or a left turn, then $\nu
e(s)$ is $-1$ if $s$ is the initial state of $e$, $+1$ if $s$ is the final state, and $0$ otherwise\foot\dag{\bf again, slight trouble if the endpoints are the same: $\nu
e(s)$ should be zero then.}. We then define
$$\nu
T(s)=\sum
e \kappa
T(e)\nu
e(s)$$
By a variant of Euler's theorem, we can conclude that the signed multiset $T$ corresponds to a closed tour if and only if $\nu
T(s)=0$ for all $s\in W$.

If $\mu$ and $\tau$ are counting functions derived from a partial tour, then we can compute $\nu$ from them directly in the following way: for any state $s$, let $m
s(\alpha)$ be the state having same tangent as $s$ and position $\po s + \alpha\cdot\di s$. Similarly, define $t
s(\alpha)$ as the state having position $\po s$ and whose direction is that of $s$ rotated counterclockwise by an angle $\alpha$. Then
$$\twoline{\nu(s)=\lim
{\alpha\to 0-}\tau(t
s(\alpha))-\lim
{\alpha\to 0+}\tau(t
s(\alpha))}{3pt}{+\lim
{\alpha\to 0-}\mu(m
s(\alpha))-\lim
{\alpha\to 0+}\mu(m
s(\alpha))}$$

{\bf define winding number by looking at $\mu$, degree by looking at $\tau$.}

{\bf define addition, negation and multiplication by an integer by acting on $\mu$ and $\tau$? or on $w$ and $\delta$? either one requires the other be proved as a theorem.}

{\bf proof that addition produces a tracing:} we take two tours $T
A$ and $T
B$ describing $A$ and $B$, and an arbitrary path $\pi$ from the initial state of $A$ to that of $B$. The concatenation of $T
A$, $\pi$, $T
B$, and finally $\pi$ in reverse gear is a tour of $A+B$.

{\bf Attempt to define general fibration direct from tracings (warning: still ugly and buggy)}: given $\phi\in W\times W\to W$, and $\lambda
{ij}\in W\times W\to \integers$, where $i,j\in\set{1,2}$, the associated fibration is an operation that given two tracings $A, B$ returns the tracing $A\circ B$, defined by
$$\twoline{[\mu
{A\circ B}(s),\tau
{A\circ B}(s)]}{5pt}{=\sum
{{r,t\in W}\atop{s=\phi(r,t)}}[\mu
A(r),\tau
A(r)]\times[[\lambda
{ij}(r,t)]]\times[\mu
B(t),\tau
B(t)]^T}\eqno(\Eq8)$$

An important property of this definition is that $A\circ B$ is bilinear, i.e. distributes over addition: $(A
1+A
2)\circ B=A
1\circ B + A
2\circ B$, and symmetrically for $B$.

{\bf What conditions should the fuctions $\phi$ and $\lambda$ satisfy?} A condition seems to be that for any two legs $e,f$, the values of $\lambda
{ij}(r,t)$ are nonzero only on finitely many pairs $r\in e$ and $t\in f$. In the case of convolution, the pairing is
$$\lambda
{11}(r,t)=0, \lambda
{12}(r,t)=\lambda
{21}(r,t)=\lambda
{22}(r,t)=1$$
if $r$ and $t$ are parallel, and $0$ otherwise.

{\bf Fibration defined in terms of a decomposition of the tracing into legs:} Consider a function $M$ that given two legs $e,f$ returns a partial tracing $M(e,f)$ with the property that $M$ is bilinear, i.e. if we break a leg $e$ into two legs $e
1$ and $e
2$ then $M(e,f)=M(e
1,f)+M(e
2,f)$, and similarly for $f$. Then $M$ can be extended to take two partial tracings and deliver a third, by
$$M(A,B)=\sum
{e,f\,{\char l\char e\char g\char s}} \kappa
A(e)\kappa
B(f)M(e,f).$$

For convolution $M$ is the following: $M(e,f)$ is $e\ast f$, i.e. is the null tracing if $e$ and $f$ are both moves, is $e$ translated by the position of $f$ if $e$ is a move and $f$ is a matching turn (or vice-versa if vice-versa) and is the intersection of the two turns at the sum of the two positions if both are turns. This can be summarized by the formulas
$$\eqalign{\mu
{e\ast f}(s)=\sum
{{r\in W}\atop{r\relvv s}}\mu
e(r)\tau
f(s-r)+\mu
f(r)\tau
e(s-r)\cr\vsk6
\tau
{e\ast f}(s)=\sum
{{r\in W}\atop{r\relvv s}}\tau
e(r)\tau
f(s-r)\cr}\eqno(\Eq9)$$
which agrees with formula (\Eq8).

From the bilinearity property it follows that equations (\Eq9) hold also with $A$ and $B$ substituting $e$ and $f$. Notice that this works without any transversality assumption, thanks to the one-half convention for terminal states. The rules of the road are obvious consquences of the signed multiplicity conventions and the fact that said multiplicities are multiplied (argh!) in formula (\Eq9). (try it! seems too nice to be true).

For product, it seems we can define $M(e,f)$ by considering the winding function $w
e(p)$ of a move $e$ to be

\item zero everywhere if $e$ is a turn or an horizontal move;

\item one if $e$ is a forward move oriented upwards and $p$ is to the left of $e$;

\item one half if $e$ is a forward move oriented upwards and $p$ is to the left of one of its endpoints, or on $e$;

\item minus those amounts if $e$ is a forward move oriented downwards;

\item zero otherwise.

Then the product $e\times f$ is the tracing in with every state $s$ gets $\mu
{e\times f}(s)$ equal to $\mu
e(s)w
f(\po s)+\mu
f(s)w
e(\po s)$, and $\tau
{e\times f}(s)=\mu
e(s)w
f(\po s)+\mu
f(s)w
e(\po s)$ plus an extra term that creates the extra turns at the intersection of two moves. {\bf hunch: this extra term may depend on the degree function $\delta
e(\lscr)$, or some other related function, which apparently should count the number of final minus initial endpoints of $e$ to the left of $\lscr$.}

{\bf can we cook things (by mixing $\mu$ and $\delta$ and $w$ and $\tau$) so that $w$'s get ${1\over2}$ (or ${1\over4}$) consistently at intersections of moves?}

{\bf the main alternatives for defining the operations of convolution, product, etc. are:} (1) Functional definition (product is such that $w$'s multiply, convolution is such that fundamental theorem holds, etc.); depends on good definition for product and a lot of public relations. (2) Definition by some magic formula involving $\mu
A$ and $\mu
B$, like (\Eq8) or (\Eq9); obscure but succint (?). (3) Definition by decomposition into legs and bilinearity: clear how to compute, but prolix (all combinations of leg types to consider) and not so intuitive as for what it means.