\input TR8TwoColFormat.tex \input GeoMacros \input KineMacros

\begfile{KineticExtraIV.tex of December 14, 1983 3:48 am --- Stolfi}

\pagetitlestuff{

\title{Kinetic Framework Extras\cp IV. Tracing on the Cartesian Unit Sphere}

%  Inspired by the Kinetic Framework paper (FOCS '83)

\author{Jorge}

}

\columntitlestuff{

\abstract{Indeed.}

}

 % ADDITIONAL MACROS

% Other

\def\der{\mathop{\char d}}
\def\tu{\tau}
\def\foobars{\Fscr}
\def\bv{\basis}
\def\sd{\sdist}
\def\ad{\adist}
\def\dt{{{d}\over{dt}}}
\def\f#1{\hbox{\fx #1}}
\def\S#1{{\sphere
{#1}}} % sphere

\def\xvec{\hbox{\bf x}}
\def\yvec{\hbox{\bf y}}
\def\zvec{\hbox{\bf z}}

 \section{\Sec1. The Cartesian unit sphere}

 \subsection{\Sec2.2 Trajectories.}

In the rest of this section we will try to define the notion of a {\it trajectory} in the space $\states$ of all states. 
Intuitively, a trajectory describes a motion of the car during some some time interval.  We want to consider only motions where the 
position and tangent are smooth functions of time, and such that at every time the velocity of the car is colinear with its 
tangent. We do not want to rule out corners and cusps, however. 

Imagine that the car describes such a trajectory $s\in[t
0\sp t
1]\mapsto \states$, and consider the motion of the two normalized 
vectors $[\po s]$ and $[\ta s]$ (both functions of time). Each describes a trajectory on the unit sphere. The condition that the 
velocity be colinear with the tangent says that $[\po s]$ moves always in the plane perpendicular to $[\ta s]$, that is, $(\dt[\po 
s])\perp[\ta s]$, where $\dt$ means derivative with respect to time. On the other hand, since the tangent has to pass through the 
point at all times, the plane perpendicular to $[\ta s]$ must turn (if at all) around the vector $[\po s]$. This means the vector 
$[\ta s]$ moves always in the plane perpendicular to $[\po s]$, that is, $(\dt[\ta s])\perp[\po s]$ at all times. Now $[\po s]$ and 
$[\ta s]$ have constant (unit) length, so we must also have $(\dt[\po s])\perp[\po s]$ and $(\dt[\ta s])\perp[\ta s]$. Therefore, 
$\dt[\po s]$ and $\dt[\ta s]$ are colinear with the vector product $[\po s]\times[\ta s]$. Therefore, they satisfy the differential 
equation
$$\eqalign{
  \dt [\po s]=\msp[\ta s]\times[\po s]\cr
  \dt [\ta s]=\tsp[\po s]\times[\ta s],\cr} \eqno(\Eq1)$$
where $\msp,\tsp$ are two suitable functions from $[0\sp T]\mapsto \reals$, called the {\it homogeneous speed} and {\it homogeneous 
dual speed}, repectively. 

To understand what those functions mean, consider a the value of $s$ at a given instant $t\in [t
0\sp t
1]$ as representing also an 
``homogeneous car'', placed on the unit sphere at the point $[\po s]$, and facing along the oriented great circle that projects 
onto the line $\ta s$. In other words, the hood of the car points in the direction of the vector $[\ta s(t)]\times[\po s(t)]$. 
After an infinitesimal instant $dt$ the car will have moved $\msp(t)\cdot dt$ in the direction $[\ta s](t)\times[\po s](t)$, 
perpendicular to the plane of $[\ta s]$ and $[\po s]$. In the same interval, the dual vector $[\ta s]$ will have moved 
$\tsp(t)\cdot dt$ in the opposite direction. The two vectors $[\ta s](t)$ and $[\po s](t)$ then will have rotated around the {\it 
homogeneous center of curvature}, the vector
$$\eqalign{[\center]  = [\tsp[\po s] + \msp[\ta s]]\cr
 \null  = {{\tsp[\po s] + \msp[\ta s]}\over{\sqrt{\tsp^2 + \msp^2}}}\cr}$$

Note that $\center$ is a function of $t$ and is not defined when $\sqrt{\tsp^2 + \msp^2}$ is nonzero, that is, when $\msp$ and 
$\tsp$ are both zero. The two vectors $[\ta s](t)$ and $[\po s](t)$ turn around the line of $[\center(t)]$ at the angular speed 
$\sqrt{\tsp^2 + \msp^2}$, in radians/unit time. This is also the angular speed of the vector $[\ta s(t)]\times[\po s(t)]$; since 
the latter is perpendicular to $\center$ and of unit length, its linear speed is $\sqrt{\tsp^2 + \msp^2}$. We call this quantity 
the {\it total homogeneous speed} of the car at each instant. 

The {\it homogeneous length}, the {\it homogeneous dual length}, and the {\it homogeneous motion} of the trajectory in the interval 
$[t
0\sp t
1]$ are defined as the integrals
$$\int
{t
0}^{t
1} \msp, \hfil \int
{t
0}^{t
1} \tsp, \hfil \int
{t
0}^{t
1} \sqrt{\tsp^2 + \msp^2}$$
These are the lengths of the curves described by $[\po s]$, $[\ta s]$, and $[\ta s]\times[\po s]$ on the sphere during that 
interval.

{\bf STOPPED HERE December 14, 1983 3:48 am}

\begitems

\item $\mu> 0$, $\tau=0$: The car is moving forwards in a straight line.

\item $\mu>0$, $\tau>0$: The car is moving forwards and turning counterclockwise, along a ``D-shaped'' curve. 

\item $\mu=0$, $\tau>0$: The car is turning counterclockwise without moving.

\item $\mu<0$, $\tau>0$: The car is moving backwards and turning counterclockwise, along a ``C-shaped'' curve.

\item $\mu<0$, $\tau=0$: The car is moving backwards in a straight line.

\item $\mu<0$, $\tau<0$: The car is moving backwards and turning clockwise, along a ``D-shaped'' curve.

\item $\mu=0$, $\tau<0$: The car is turning clockwise without moving.

\item $\mu>0$, $\tau<0$: The car is moving forwards and turning clockwise, along a ``C-shaped'' curve.

\item $\mu=0$, $\tau=0$: The car is standing still.

\enditems

If $\pos s$ is not the top origin, the above interpretation of $\mu(t)$ and $\tau(t)$ is no longe valid, since the central 
projection that maps the unit sphere on the Cartesian plane will distort angles and distances. As long as $\po s$ is on the top 
side, the meaning of the signs of $\mu$ and $\tau$ will be as given above, but the numerical values of the linear and angular 
velocities, and of the radius of curvature, will have more complex formulas that depend on both $\po s$ and $\ta s$.

\note{Write them explicitly!}

For another interpretation, let us consider a car placed on the unit sphere (at the point $[\po s]$ and facing in the direction of 
the vector $[\ta s]\times[\po s]$ (so that the ``oriented great circle'' pasing through the car axis is perpendicular to $[\ta s]$ 
and oriented counterclockwise around it). Then $\mu(t)$ and $\tau(t)$ are at all times the linear and angular velocities, of the 
car, and the radius of curvature is given by ${\leftv \tau\rightv} \over{\sqrt{\mu^2+\tau^2}}$. The value of $\tau(t)$ is also the 
linear velocity of the vector $[\ta s(t)]$. \note{Justify all of this!}

Equation (\Eq1) and the accompanying discussion are valid only for motions where both $[\po s]$ and $[\ta s]$ are differentiable 
functions of time. Before continuing, we will try to weaken this requirement. Consider again the motion of the car on the unit 
sphere corresponding to the trajectory $s(t)$, where $t$ varies from $t
0$ to $t
1$. The point $[\po s(t)]$ will describe a curve 
on the sphere. We define the {\it homogeneous arc length} of the trajectory $s(t)$ between two instants $t
0$ and $t
1$ as being 
the integral
$$ \lambda{\left|{{t
1}\atop{t
0}}\right.}=\int
{t
0}^{t
1} \mu(t)\,dt,$$
that is, the integral of the {\em signed} velocity of the car between the two instants.  Note that in the classical theory, the arc 
length is the integral of the {\it absolute value} of the velocity of $[\po s(t)]$; this classical arc length is therefore always 
increasing with time. In the new framework, however, we distinguish between the parts of the curve traced by the car moving 
forwards, and those traced backwards, and take the length of the latter with a minus sign.

Similarly, we define the {\it homogeneous turning angle} of the trajectory$s(t)$ between two instants $t
0$ and $t
1$ as
$$\theta{\left|{{t
1}\atop{t
0}}\right.}=\int
{t
0}^{t
1} \tau(t)\,dt.$$
It measures how many radians the car turned (on the sphere) relative to itself in that interval, where we count clockwise turns as 
negative and counterclockwise turns as positive.

The functions $\mu(t)$ and $\tau(t)$ are then the derivatives of $\lambda(t)$ and $\theta(t)$, and therefore a trajectory is 
determined by a state $s(t
0)$ and the functions $\lambda{\left|{{t}\atop{t
0}}\right.}$  and 
$\theta{\left|{{t}\atop{t
0}}\right.}$ as a function of $t$. The advantage of doing this is that we can define the trajectory for 
{\it any} two continuous functions $\lambda$ and $\theta$, even if their derivatives are not defined. This is shown by the 
construction below.

 {\bf STOPPED HERE September 27, 1983 11:10 pm}

Let $f$ be a function with domain $T\subset\reals$. For any $t\in \reals$, we define
$$\eqalign{
  f(t\xp
T)=\lim
{{x\to t}\atop{x>t}} (x\in T)f(x),\cr
  f(t\xm
T)=\lim
{{x\to t}\atop{x<t}} (x\in T)f(x),\cr}\eqno(\Eq2)$$
and we write just $f(t\xp)$ and $f(t\xm)$ when $T$ is implicit from the context. The function $f$ is said to be {\it frumious} if 
$f(t\xp)$ and $f(t\xm)$ are defined and finite for all $t\in \reals$. Two functions $f,g$ of real argument are {\it frumiously 
equivalent} if $f(t\xpm)=g(t\xpm)$ for all $t\in \reals$. \foot\sectionmark{What a frumious function should be exactly is not yet 
clear, and probably depends on what we want to do with the tracings later on. We want it to be bounded, suitably smooth and 
well-behaved, but we must be prepared to accept at least a finite number of discontinuities. Maybe we can even accept unbounded 
functions if they are integrable.} 

\definition{\Def1}{A {\it trajectory} is a function $s$ of some interval $T$ of the real line into the set of all states, such that 
the homogeneous coordinates of $s$ (considered as two vectors of $\reals^3$) satisfy 
$$\eqalign{
  {{\der {\po s}}\over{\der t}}(t\xpm)=\mu(t\xpm)(\ta s(t\xpm)\times \po s(t\xpm))\cr
  {{\der {\ta s}}\over{\der t}}(t\xpm)=\tu(t\xpm)(\po s(t\xpm)\times \ta s(t\xpm)),\cr} \eqno(\Eq1)$$
where $\mu(t),\tu(t)$ are frumious functions from $T\mapsto\reals$, and $\times$ denotes vector product.}

\theorem{\Th1}{For any pair of frumious functions $\mu,\tu$, and any boundary condition of the form $s(t
0)=s
0\in\states$, there 
exists a unique pair of continuous functions $\po s, \ta s$ from $\reals\mapsto\reals^3$ that satisfy equation (\Eq1).}
\proof{We can always fix the definition of frumious to make it happen, can't we?}

\theorem{\Th2}{Let $\po s(t), \ta s(t)$ be a pair of continuous functions from $\reals\mapsto \reals^3$ satisfying equation (\Eq1). 
Then the lenghts of $\po s(t)$ and $\ta s(t)$, and their dot product $\po s(t)\cdot\ta s(t)$ are independent of $t$}
\proof{From equation \Eq1, the derivatives of $\po s(t)$ and $\ta s(t)$ are frumiously orthogonal to them. Since the two are 
continuous, their lengths are constant. As for the dot product, we have
$$\eqalign{ {\der \over{\der t}}(\po s\cdot\ta s)
  =\po s\cdot{{\der \ta s}\over{\der t}}
    +{{\der \po s}\over{\der t}}\cdot\ta s\cr
  \null=\tu[\po s\cdot(\po s\times\ta s)]+\mu[(\ta s\times\po s)\cdot\ta s]\cr
  \null=0.\cr}$$

\pp Is that it?}

\corollary{\Th3}{Let $\po s(t), \ta s(t)$ be as in theorem \Th2. If for some $t
0$ the two vectors are the homogeneous coordinates 
of a valid state $s(t
0)$, then $s(t)$ is a valid state for all $t\in \reals$. Furthermore, if the coordinates are normalized at 
time $t
0$, they are normalized for all $t$.}

The {integral} of a frumious function A frumious function is {\it of finite measure} if its  We define a {\it 
foobar}\foot\dag{Second-order state? Complete state? Second-order germ?} $s$ consists of a {\it base state} $\ba s$ plus a {\it 
curvature} $\cu s$. The curvature is a point of the two-sided line $\hop{\mu \hom \tau}$. Intuitively, a foobar describes the 
instantaneous state of a car: the position is the point of the plane where the car is, the tangent gives the the direction in which 
its hood is facing, and the curvature describes the direction in which the car is moving and turning, according to the following 
table:

By ``normalized'' we mean that $\mu^2(t)+\tu^2(t)=1$ at all times (except at the discontinuities, if any). This implies boundedness 
and helps making the parametrization unique. I doubt whether the latter has any advantage, but equation (\Eq1) gives always 
normalized coordinates for $\po s$ and $\ta s$, so why not ...

Then we have

\item $\mu> 0$, $\tau=0$: The car is moving forwards in a straight line (infinite radius of curvature);

\item $\mu>0$, $\tau>0$: The car is moving forwards and turning counterclockwise, along a ``D-shaped'' curve;

\item $\mu=0$, $\tau>0$: The car is turning counterclockwise without moving (zero radius);

\item $\mu<0$, $\tau>0$: The car is moving backwards and turning counterclockwise, along a ``C-shaped'' circular arc  with radius 
$\leftv\mu/\tau\rightv$;

\item $\mu<0$, $\tau=0$: The car is moving backwards in a straight line (infinite radius of curvature);

\item $\mu<0$, $\tau<0$: The car is moving backwards and turning clockwise, along a ``D-shaped'' circular arc with radius 
$\leftv\mu/\tau\rightv$;

\item $\mu=0$, $\tau<0$: The car is turning clockwise without moving (zero radius);

\item $\mu>0$, $\tau<0$: The car is moving forwards and turning clockwise, along a ``C-shaped'' circular arc with radius 
$\leftv\mu/\tau\rightv$.

In summary, the sign of $\mu$ tells whether the car is moving forwards or backwards, the sign of $\tau$ whether it is turning 
counter- or clockwise, and the ratio $\leftv\mu/\tau\rightv$ is the current radius of curvature.

The set of all possible foobars, that is, all possible triplets of a point, a tangent through it, and a radius of curvature, will 
be denoted by $\foobars$. The homogeneous metrics on the points and lines of the 2SP and on the points of the two-sided line define 
a topology for $\foobars$.

We define the {\it time reversal\/}\foot\bullet{Antichrone? (ugh!)} of a state $s$ as being the state $\ne s$ with same position 
and tangent, but whose curvature is the {\it antipodal} of $\cu s$. That is, if the curvature of $s$ is $\hop{\mu\hom \tau}$, the 
curvature of $\ne s$ is $\hop{-\mu\hom -\tau}$. The state $\ne s$ represents the car being in the same position and facing the same 
way as $s$, and turning along the same circle, but in the opposite direction.

 \subsection{\Sec2.1. Signed multisets} 

A {\it signed multiset} is a generalized multiset, in which the multiplicity of the elements are arbitrary real values, possibly 
fractional and/or negative. Formally, a signed multiset $M$ is simply a function $M$ from some set {\it base set} $\bar M$ into 
$\reals$. From now on, all multisets are assumed to be signed. 

We consider two multisets to be the same if every element that occurs in one of them {\it with nonzero multiplicity} also occurs in 
the other with the same multiplicity, and vice-versa. In other words, we do not distinguish between the case where $x$ is not in 
$\bar M$, and the case where $x$ is in $\bar M$ but has multiplicity zero in $M$. As a matter of fact, the ``base set'' is a purely 
technical device, that plays no further role in this paper.

More formally, we assign to the expression ``$x\in M$'' {\it numerical} value, equal to the multiplicity of $x$ in $M$. We consider 
two multisets $M,M\pr$ to be the same if $x\in M \,=\, x\in M\pr$ for all $x$. Using this notation, we also define summation over 
the elements of a multiset by the identity
$$\sum
{s\in M} f(s) = \sum
{s\in {\bar M}} (s\in M)\cdot f(s)$$
These conventions are helpful in writing summations over complex ranges. In the few contexts where ``$s\in M$'' is used as a 
predicate, it should be read as ``the multiplicity of $s$ in $M$  is non-zero''.

The (only) multiset where every element has zero multiplicity is {\it empty multiset} $\empty$. The operations of addition, 
subtraction, and multiplication by a real value are defined for multisets in the obvious way. A multiset is said to be {\it 
integral} if all its elements have integer multiplicities (positive or negative). 

When dealing with multisets of states we will consider each occurence of a state $s$ as being equivalent to {\it minus one 
occurence of the state $\ne s$}, and vice-versa. More formally, we define the numerical value of $s\in M$ for a state $s$ as being 
{\it the multiplicity of $s$ in $M$ minus the multiplicity of $\ne s$ in $M$}. So, we always have
$$ s\in M\;=\;-(\ne s\in M)$$
for any state $s$. This convention is used also when comparing multisets of states. In particular, if in a multiset $M$ every state 
occurs as many times as its negative, then we consider $M=\empty$. \note{Is this too ugly? I could have used the one-sided line 
plus the point at infinity as the range of curvatures, but then curvatures would no longer form a continuum; there would have to be 
a break at some arbitrary point.}

 \subsection{\Sec2.3 Legs}

The position, tangent and curvature of a state $s$ define a unique {\it oriented circle} on the 2SP, the {\it circle of $s$}.  is 
the collection of all states that would be traversed by a car that

 {\bf STOPPED HERE September 1, 1983 12:52 am}

Let $r, s$ be two states with same curvature. \note{The convolution of two tracings is defined only if the states with tangents at 
infinity have multiplicity zero.}

 \subsection{\Sec2.1. Polygonal trips and tours}

$M, M\pr$ are two multisets of states, we as being a continuous one-to-one function from the interval $[0\sp 1]$ into $W$, such 
that all states $m(t)$ have the same tangent line, and the positions $\po m(t)$ span a proper (and nonzero) arc of that line. A 
{\it turn} is similarly a continuous one-to-one map $n$ from some closed interval $T$ into $W$ such that all states $n(t)$ have the 
same position, and their tangent lines span a proper angle with vertex at that point. We denote a move or turn that begins at state 
$r$ and ends at state $s$ by $[r\to s]$. The restriction to proper arcs and angles makes the sequence of states unambiguous. This 
notation leaves the base interval $T$ unspecified, but that is irrelevant for what follows; we can always assume it to be $[0\sp 
1]$.\note{Note that a move can cross the line at infinity, or lie on it; continuity is defined by the homogeneous metric.}

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 
define the concept of a {\it trip}, which is a parametric representation of a generalized curve.

Intuitively, a trip can be viewed as the description of a car trip on the plane. We restrict our attention at first to trips in 
which the trajectory of the car is a polygonal line with finitely many sides. At any moment during such trip, the car is at a 
definite point on the plane, and is facing in a definite direction; this point and this direction together are constitute the 
``instantaneous state'' of the car.

Formally, we define a {\small\it first-order} {\it state} $s$ as consisting of a {\it position} $\po s$, which is a point of the 
2SP, and a {it tangent} $\ta s$, which is an oriented line of the 2SP passing through $\po s$. The orientation of the tangent line 
is the {\it orientation} of the state, and is denoted by $\di s$; this is undefined if the tangent line is the line at infinity. 
\note{The convolution of two tracings is defined only if the states with tangents at infinity have multiplicity zero.} The set of 
all possible states, that is, all possible pairs of a point and a tangent through it, will be denoted by $W$. The homogeneous 
metric on the points and lines of the 2SP determine a topology for $W$; under this tpology, $W$ is homeomorphic to $\S2\times \S1$. 
\note{That is right, isn't it?}

The polygonal trips we are going to consider consist of a finite sequence of ``legs'', which roughly correspond to the sides and 
vertices of the polygonal trajectory. During each leg of the trip, the car either moves in a consitent direction along its current 
tangent line (forwards of backwards), or turns in a consistent direction (right or left) while its position remains fixed. In the 
formalization of this concept that is given below, we will not be interested in the details of the movement of the car along each 
leg. All we want to capture is the {\it sequence} of states the car passed through in during its trip. 

We define a {\it move} as being a continuous one-to-one function from the interval $[0\sp 1]$ into $W$, such that all states $m(t)$ 
have the same tangent line, and the positions $\po m(t)$ span a proper (and nonzero) arc of that line. A {\it turn} is similarly a 
continuous one-to-one map $n$ from some closed interval $T$ into $W$ such that all states $n(t)$ have the same position, and their 
tangent lines span a proper angle with vertex at that point. We denote a move or turn that begins at state $r$ and ends at state 
$s$ by $[r\to s]$. The restriction to proper arcs and angles makes the sequence of states unambiguous. This notation leaves the 
base interval $T$ unspecified, but that is irrelevant for what follows; we can always assume it to be $[0\sp 1]$.\note{Note that a 
move can cross the line at infinity, or lie on it; continuity is defined by the homogeneous metric.}

We call a move {\it forward} or {\it backward} depending on whether the point $\po m(t)$ as $t$ increases moves in agreement with 
the orientation of the tangent $\ta m(t)$, or in opposition to it. A turn is left or right depending on whether the tangent line 
$\ta n(t)$ turns counter- or clockwise as $t$ increases. \note{Define time reversal}.

Let $f,g$ be two functions from the closed intervals $[0\sp u]$  and $[0\sp v]$, respectively, into an arbitrary set $X$. If 
$f(u)=g(0)$, we say that a function $h: [0\sp u+v]\mapsto X$ is the {\it concatenation of $f$ and $g$} if $h(x)=f(x)$ for $x\in 
[0\sp u]$, and $h(x+u)=g(x)$ for $x\in[0\sp v]$. The {\it time reversal} of $f$ is the function $h=\neg f: [0\sp u]\mapsto X$ such 
that $h(u-x)=f(x)$ for all $x$ in $[0\sp u]$. The function $f$ is {\it cyclic} ({\it closed}?)if $f(u)=f(0)$.

We then define a polygonal trip as any function that is the concatenation of a finite number of moves and turns. A trip is then a 
continuous function from some closed interval $[0, w]$ of the real line into the set of all states. If the function is cyclic 
(i.e., it ends and begins at the same point and with the same orientation), the trip is called a {\it polynomial tour}. 

 \subsection{\Sec2.2 Polygonal tracings}

We will define tracing as an even more abstract description of a polygonal tour, a description that seeks to preserve the 
geometrical and topological features of the trip while omitting practically all timing information. The tracing determined by a 
trip 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 trips to describe the same tracing. 

A tracing $T$ will be 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 {\it polygonal tracing} if 
and only if they are obtained from some polygonal trip by the above rules.

The precise definition of $\mu$ and $\tau$ are as follows. For a single forward move $m=[a\to b]$, we define the moving count 
$\mu
m(s)=+1$ if $s$ is an interior state of $m$ (that is, if $z=m(t)$ for some $t\in (0\sp 1)$, $\mu
m(s)=+{1\over2}$ if $s=a$ or 
$s=b$, and $\mu
m(s)=0$ if $s$ does not occur in $m$. If $m$ is a backward move, the values of $\mu
m$ are the negatives of the 
above: $-1$ for internal states, $-{1\over 2}$ for the endstates, and $0$ for all other states of $W$. In either case, the turning 
count $\tau
m(s)$ is zero for all states $s$ in $W$.

The counting functions for a single turn $n$ are defined in a similar way. If $n=[a\to b]$ is a left (counterclockwise) turn, then 
$\tau
n(s)=+1$ for any ``internal'' state $s=n(t)$ with $t\in(0\sp 1)$; $\tau
n(s)=+{1\over2}$ if $s$ is an end state ($s=a$ or 
$s=b$); and $\tau
n(s)=0$ if the state $s$ does not occur in $n$. For a right turn, these numbers are negated: $\tau
n(s)$ is $-1$ 
for internal states, $-{1\over2}$ for the end states, and $0$ for the rest. In any case, the moving count $\mu
n(s)$ is zero for 
all $s$. \note{Note that this definition requires moves and turns to have nonzero length and be strictly less than the whole line. 
Similarly, turns must make a nonzero angle less than $2\pi$. The notation $[a\to b]$ restricts further moves to proper arcs and 
turns to less than $\pi$.}

The functions $\mu
T$ and $\tau
T$ for the whole tour are simply the algebraic sum of the functions $\mu
e$ and $\tau
e$ for all 
legs of the tour $T$. Clearly, the speed with which the car covered each leg of a tour does not affect the corresponding tracing. 
The tracing is also unaffected by subdividing moves or turns. For example, if we break a move in two consecutive ones at a internal 
state $s$, this state 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, 
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{\Sec2.3. Characterization of (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. 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{\Sec2.4. Winding number and degree}

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

 \section{\Sec3. Operations on tracings}

 \subsection{\Sec3.1 Addition and related operations}

\note{Define  addition, negation and multiplication by an integer by acting on $\mu$ and $\tau$. Must prove theorem of addition of 
winding numbers, and degrees.}

The addition of two complete polygonal tracings is complete, since $\nu
{A+B}=\nu
A+\nu
B= 0$.  We can see why this is true by 
considering two tours $T
A$ and $T
B$ corresponding to the tracings $A$ and $B$, and an arbitrary path $\pi$ from the initial state 
of $T
A$ to that of $T
B$. The concatenation of $T
A$, $\pi$, $T
B$, and finally $\neg\pi$ is a tour of $A+B$.  

 \subsection{\Sec3.2 Fiber products}

A {\it fibration of states} is a function that for each pair $r,s$ of states gives a resultant state $\phi(r,s)$ and eight integer 
coefficients $M
{ij}(r,s), T
{ij}(r,s)$ where $i, j\in\set{\f{m}, \f{t}}$. Given a state fibration $\phi,\lambda
{ij}$, we define 
the associates {\it fiber product} as an operation that given two tracings $A, B$ returns the tracing $A\circ B$, defined by
$$\eqalign{
 \mu
{A\circ B}(s)=\sum
{{r,t\in W}\atop{s=\phi(r,t)}} 
       M
{\f{mm}}\mu
A(r)\mu
B(t)+M
{\f{mt}}\mu
A(r)\tau
B(t)\cr
   +  M
{\f{tm}}\tau
A(r)\mu
B(t)+M
{\f{tt}}\tau
A(r)\tau
B(t)\cr}
 \eqno(\Eq8)$$
and
$$\eqalign{
 \tau
{A\circ B}(s)=\sum
{{r,t\in W}\atop{s=\phi(r,t)}}T
{\f{mm}} 
       \mu
A(r)\mu
B(t)+T
{\f{mt}}\mu
A(r)\tau
B(t)\cr
   +  T
{\f{tm}}\tau
A(r)\mu
B(t)+T
{\f{tt}}\tau
A(r)\tau
B(t),\cr}
 \eqno(\Eq8)$$
or in matrix form
$$\mu
{A\circ B}(s)=\sum
{{r,t\in W}\atop{s=\phi(r,t)}}[\mu
A(r),\tau
A(r)]\times M\times[\mu
B(t),\tau
B(t)]^\Tscr\eqno(\Eq8)$$
and
$$\tau
{A\circ B}(s)=\sum
{{r,t\in W}\atop{s=\phi(r,t)}}[\mu
A(r),\tau
A(r)]\times T\times[\mu
B(t),\tau
B(t)]^\Tscr\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.

 {\bf JUNK}

% Begin

i. $s(t)$ is continuous (in the $\hdist$ metric);

ii. The derivatives any instant either the the interval $T$ can be decomposed into a finite number of pieces such that in each 
piece either $\po s(t)$ or $\di s(t)$ (or both) is constant; and

ii. the velocity vector ${d\over{dt}}\po s(t)$ is colinear with the tangent  Intuitively, these conditions state that the car moves 
smoothly and always parallel to its longitudinal axis (that is, it cannot skid). Formally, if $\po s(t)=\hop{x(t), y(t)\hom w(t)}$ 
and $\ta s(t)=\hol{X(t), Y(t)\hom W(t)}$, then the functions $x(t), y(t), w(t), X(t),Y(t)$, and $W(t)$ must be continous and 
differentiable, and we must have
$$X(t)x(t)+Y(t)y(t)+W(t)w(t)=0\eqno(\Eq{10})$$
(that is, $\po s(t)$ is on $\ta s(t)$),
$$X(t)x\pr(t)+Y(t)y\pr(t)+W(t)w\pr(t)=0\eqno(\Eq{11})$$
(that is, the velocity vector ${d\over{dt}}\po s(t)$ is parallel to $\ta s(t)$), and
$$X\pr(t)x(t)+Y\pr(t)y(t)+W\pr(t)w(t)=0\eqno(\Eq{12})$$
(that is, $\ta s(t)$ is turning around the point $\po s(t)$). \note{the last two conditions are equivalent to each other, given the 
first one. Is the first condition implied by the other two (given the right initial condition)?}

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.A {\it tour} is a closed trip, one that ends in the same state (position and tangent) by which it began. \note{And whose 
derivatives at either end are the same. Can we get by with only piecewise differentiability, or Liebnitz differentiability, or 
something of the sort, instead of total differentiability of $x(t), y(t)$ etc}?

We can break the interval $T$ 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.
\figspace5cm

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.

\note{Let $X$ be any set. Let $F
X$ be the set of all $X$-valued functions whose domain is any closed interval of the real line.  
For any $f,g\in F
X$, with domains $[a\sp b]$ and $[c\sp d]$ respectively, we define $f\approx g$ iff there is a $C^1$ 
monotonically increasing  mapping $h:[a\sp b]\mapsto [c\sp d]$ with $g(x)=f(h(x))$ for all $x$. 

I A {\it time sequence} of elements of $X$} is an equivalence class of $\approx$. Clearly all equivalent functions have the same 
initial and final values, which are by definition the inital and final values of the time sequence. If $\hat f$ and $\hat g$ are 
two time sequences of elements of $X$ corrsponding to the functions $f:[a, b]\mapsto X$ and $g: [c, d]\mapsto X$, and $f(b)=g(c)$, 
we define concatenation of $\hat f$ and $\hat g$ as the equivalence class under $\approx$ of the function
$$h(x)=\alter{f(x) \rmiff x\in [a,b],\cr
g(x-b+c) \rmiff x\in [b, b+(d-c)]\cr}$$

 {\bf JUNK}


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.

 {\bf GARBAGE GENERATED ON September 28, 1983 7:23 pm}

So, for example, the quantity $u\cdot[v]$ is the component of $u$ in the direction $v$; the quantity $[u]\cdot[v]$ is the cosine of 
the angle between the vectors $u$ and $v$.

\par\vfill\eject\end