\input TR8TwoColFormat \input GeoMacros \input KineMacros

\begfile{KineticExtraIII.tex of December 6, 1983 3:26 am --- Stolfi}

% Elucubrations on the Kinetic Framework for abstract submitted to FOCS 83
%  Used to be called [Ivy]<Stolfi>Cg>ConvExtra.tex

\pagetitlestuff{

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

\author{J. Stolfi}

}

% ADDITIONAL MACROS

% Other

\def\cs{\mathop{\char c\char r}}
\def\ss{\mathop{\char s\char r}}

\section{\Sec2. Motivation}

\subsection{\Sbsec{\Sec2.1}. The convolution of two figures}

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

\subsection{\Sbsec{\Sec2.1}. Convolution and the outline representation}

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.

\section{\Sec3. Generalized outlines}

\subsection{\Sbsec{\Sec3.1}. States, tours, and tour elements}

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.

\subsection{\Sbsec{\Sec3.2}. Tracings}

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

\subsection{\Sbsec{\Sec3.4.5}. Complete tours and tracings}

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

\subsection{\Sbsec{\Sec3.5}. Winding number and degree}

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

\section{\Sec4. Operations on tracings}

\subsection{\Sbsec{\Sec4.1} Addition and related operations}

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

\subsection{\Sbsec{\Sec4.2} Fibrations}

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

\par\vfill\eject\end