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

An {it arc} is the sequence of states traversed by the car that moves along a circular trajectory in a consistent direction (forwards or backwards), while turning (left or right) by less than $180\deg$.

An arc is completely determined by its {\it initial} and {\it final} states. Therefore, we are justified in talking about {\it the arc from state $r$ to state $s$}, denoted by $\la r \sp s\ra$. Notice however that not every pair os states defines an arc in this fashion.

The ({\it signed}) {\it length} $\len(\alpha)$ of the arc is its length taken with $+$ or $-$ sign depending on whether the car moves forwards or backwards. The {it angle} $\ang(\alpha)$ swept by the arc is by definition measured in radians, and taken with sign $+$ or $-$ depending on whether the car turned left or right (counter- or clockwise). An arc with zero length is a {\it turn}, and one with zero angle is called a {\it move}.

The {\it measure} of the arc is by definition the non-negative quantity $\abs{\alpha}=\sqrt{\len^2+\ang^2}$. The {\it empty arc}, where the car doesn't move at all, is the only arc with coincident endstates, is the only one with zero measure, and is both a move and a turn.

\problem{\Prob{\Sbsec{\Sec1.1}.1}}{Give a necessary and sufficient condition (in terms of homogeneous coordinates) for the states $r,s$ to be the endstates of an arc.}

\problem{\Prob{\Sbsec{\Sec1.1}.2}}{Give a necessary and sufficient condition (in terms of homogeneous coordinates) for the state $s$ to be on the arc $\la r \sp s\ra$.}

\problem{\Prob{\Sbsec{\Sec1.1}.3}}{Give an efficient algorithm (perhaps of the subdivision type) to generate an arbitrarily dense and reasonably well-distrbuted set of points on the arc $\la r \sp s\ra$, assuming infinite-precision real arithmetic.}

\problem{\Prob{\Sbsec{\Sec1.1}.4}}{Given integer homogeneous coordinates for the states $r,s$, give an efficient algorithm to generate a discrete approximation to the points on the arc $\la r \sp s\ra$.}

For a non-empty arc $\alpha$, we define its {\it moving rate} $\msp(\alpha) = {{\len(\alpha)}\over{\abs{\alpha}}$ and {\it turning rate} $\tsp(\alpha) = {{\ang(\alpha)}\over{\abs{\alpha}}$. They may be interpreted as the linear and angular speeds corresponding to a trip where the car covers one unit of measure of the arc per unit of time. The unit vector $\cu \alpha= (\msp, \tsp)$ is called the {\it shape} of the arc. The shape has the following interpretation:

\begitems

\enditems

The radius of curvature of the arc is given by $\abs{\msp/\tsp}=\abs{\len/\ang}$, which is infinite when the arc is a move.

A ({\it circular}) {\it germ} $\gamma$ consists of a {\it base state} $\ba \gamma$ and a unit vector $\cu \gamma=(\msp(\gamma),\tsp(\gamma))$, the {\it shape} of the germ. Informally, we may think of the germ $\gamma$ as describing an infinitesimal arc with shape $\cu \gamma$ containing the state $\ba \gamma$. A germ therefore describes one of the many ways to pass through the state $s$ by menas of a circular arc.

With this interpretation, we can classify a germ as being {\it forwards} or {\it backwards moving}, and/or {\it left or right turning}, depending on its shape. A germ that does not turn is {\it purely moving}, and one that does not move is {\it purely turning}. The {\it time reversal} $\rev(\gamma)$ of a germ $\gamma$ is the germ having the same base state but shape $-\cu \gamma = (-\msp(\gamma),-\tsp(\gamma))$. This germ describes the car passing through $\ba \gamma$ by moving and turning in the opposite sense as $\gamma$. For succintness, we will denote the position, tangent and direction of the base state $\ba \gamma$ simply by $\po \gamma$, $\ta \gamma$, and $\di \gamma$, respectively.

The {it multiplicity} $\cnt
\alpha(\gamma)$ of a germ $\gamma$ in an arc $\alpha=\la a\sp b\ra$ is, informally speaking, the number of times the arc passes trough the state $\ba \gamma$ by an arc with curvature $\cu \gamma$, minus the number of times it passes through $\ba \gamma$ by an arc with curvature $-\cu \gamma$. More precisely, $\cnt
\alpha(s)$ is

\begitems

\enditems

An arc $\alpha$ can then be regarded as a signed multiset of germs. The {\it time reversal} of the arc $\alpha$ is the arc $\la b \sp a\ra$, that consists of the same states traversed in the opposite sequence. The multiplicity of a germ $\gamma$ in this arc is $-\cnt
\alpha(\gamma)$. Therefore, we will denote the time reversal of $\alpha$ by $-\alpha$.

A {\it tracing} is a signed multiset of germs that can be expressed as the sum of finitely many arcs, each taken with arbitrary multiplicities. A consequence of these rules is that an arc and its time reversal cancel each other out.

{\bf define $\cnt
\alpha(\gamma)\xp$ and $\cnt
\alpha(\gamma)\xp$}

A tracing is said to be {\it balanced} if for every state $s$, it the leaving multiplicities of all germs with the base state $s$ is zero, i.e.
$$\sum
{\ba \gamma=s}\cnt
T\xp(\gamma) = 0.$$
This simply means that the number of arcs entering the state is equal to the number of arcs leaving it.

A tracing is said to be {\it integral} if every germ has integer multiplicity in it.

Let $\sigma, \rho$ be two germs having parallel base states and not both purely moving. We define the {it convolution} of the two as being the germ $\gamma=\sigma\ast\rho$ such that

\begitems

\enditems

The {\it convolution} of two tracings $A$ and $B$ is defined as the tracing $A\ast B$ such that, for every germ $\gamma$, we have
$$\cnt
{A\ast B}(\gamma) = {1\over 2}\sum
{{\sigma, \rho}\atop{\sigma\ast\rho=\gamma}} \cnt
A(\sigma)\cnt
B(\rho)$$

Note that $\rev(\sigma)\ast\rho=\sigma\astrev(\rho)=\sigma\ast\rho$, and $\rev(\sigma)\ast\rev(\rho)=\sigma\ast\rho$. Therefore, for every pair $\sigma, \rho$ occuring once each in $A,B$ we also get the pair $\rev(\sigma), \rev(\rho)$ occuring $-1$ times each, giving multiplicity ${1\over2}\cdot1\cdot1+{1\over2}\cdot(-1)\cdot(-1)$ to $\gamma$. Similarly, the pairs $\sigma, \rev(\rho)$ and $\rev(\sigma),\rho$ will give multiplicity ${1\over2}\cdot1\cdot(-1)+{1\over2}\cdot(-1)\cdot1$ to $\rev(\gamma)$.

In this section we will try to generalize the results above to tracings containing curved legs (arcs). Let's restrict ourselves to legs with constant radius of curvature, i.e. arcs of circles.

The first attempt is to use the same definition of state and tracings: we assign $\mu
e(s)=1$ if the car moves forward on the arc, $-1$ if backwards; similarly, $\tau
e(s)=+1$ if it turns left, $-1$ if it turns right. These definitions are slightly discontinuous: moves and turns are not limiting cases of arcs. They seem to give the correct winding numbers and degrees. Problems:

(1) they do not fit well with the signed multiset metaphor. It is not true that every arc can be described as some signed number of copies of a forward and left-turning arc; if we accept also forward and right-turning arcs as standard generators, the symmetry between $\mu$ and $\tau$ is violated.

(2) The convolution of two forward arcs $e$ and $f$, one left-turning and one right-turning, can be either a $C$ shaped arc, a $D$ shaped one, or a turn, depending on the difference of the two radii. Therefore, the values of $\mu
{e\ast f}(s+r)$ and $\tau
{e\ast f}(s+r)$, for two parallel states $s$ and $r$ on each arc, cannot be expressed in terms of $\mu
e(s), \tau
e(s), \mu
f(r)$, and $\tau
f(r)$. This practically invalidates the fiber product approach to convolution.

A slightly modified form of this approach is to assign to an arc values of $\mu$ and $\tau$ that are dependent on the radius. Say, a circle of radius 1 gets $\mu=\tau={1\over2}$ or ${{\sqrt2}\over 2}$ or something like that. This seems to create problems with winding numbers and degrees (unless we accept that the winding number inside a circle decreases as theradius goes to zero). It is hard to evaluate this option without specifying the exact dependency of the counting functions with the radfius and the necessary modifications on the winding number, product, convolution, etc. Ideally, we should define things so that the convolution is still bilinear and definable by a local fibration.

The most promising approach seems to be to extend the notion of a state to include the current radius of curvature of the path (i.e., the position of the driving wheel). Indeed, the polygonal case is just a particularization of this approach: it is isomorphic to having a single multiplicity $\kappa(s)$ while breaking every state $S$ in two, a ``moving'' state $s
m$ and a ``turning'' one $s
t$, with $\kappa(s
m)=\mu(s)$ and $\kappa(s
t)=\tau(s)$. A tour then contains implicit ``steering'' legs between a move and a succeding turn, during which the radius of curvature changes from infinity to zero while position and orientation remain fixed.

To include circular arcs, then, the obvious approach is to recognize the existence of a continuum of states between the two extremes of pure turning and pure moving. There are two ways of doing this:

The first variant considers only the setting of the driving wheel as a parameter of the state. The continuum of states with a fixed position and direction is homeomorphic to $\sphere^1$: by decreasing the radius of curvature, a state in the middle of a $D$-shaped arc (a $D$ state) becomes a pure turning state, then a $C$ state, then a pure moving state, then a $D$ state again. The direction of motion is represented by the sign of the multiplicity $\kappa$ of the state, as before.
\figspace4cm

The problem with this variant is again that the assignment of positive and negative multiplicities must include an arbitrary discontinuity along the spectrum of curvatures, and is not simmetric in terms of turning and moving. For example, we can define the multiplicity to be $+1$ when the car is moving forward along the arc, or turning left at a turn. Then the states in a forward, right-turning arc have multiplicity $+1$ for any positive radius, but $-1$ when the radius becomes zero, a phenomenon that does not happen with forward, left-turning arcs.

The second variant then considers both the radius of curvature and the sense of motion/turning as part of the state. Surprisingly, the set of all stets with same position and orintation is still homeomorphic to $\sphere^1$: the sequence along those states is forward left-turning, forward straight, forward right-turning, pure right-turning, backwards right-turning, backwards straight, backwards left-turning, pure left-turning, forward left-turning. (Curious... This is unexpectedly similar to the general rationale behing the two-sided plane: there we were forced to break each point in two antipodal points, here we are forced to break each state in two oppositely moving pairs, in both cases to introduce some sort of orientability. Maybe this can be used as a good justification for distinguishing forward from backward moves.)\figspace 4cm