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

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.

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.

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

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

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

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

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

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

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

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

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.

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

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.

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