\input TR8TwoColFormat.tex \input GeoMacros \input KineMacros

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

\pagetitlestuff{

\title{Kinetic Framework Extras\cp VI. Circular Tracings}

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

\author{Jorge Stolfi}

}

\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. Circular tracings}

 \subsection{\Sbsec{\Sec1.0}. Arcs and tracings}

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

\item $\msp=1$, $\tsp=0$: The car is moving forwards in a straight line.

\item $\msp>0$, $\tsp>0$: The car is moving forwards and turning left (counterclockwise), describing an arc of circle that is ``D-shaped'' as seen from an observer driving the car. 

\item $\msp=0$, $\tsp=1$: The car is left without moving.

\item $\msp<0$, $\tsp>0$: The car is moving backwards and turning left, along a ``C-shaped'' arc of circle.

\item $\msp=-1$, $\tsp=0$: The car is moving backwards in a straight line.

\item $\msp<0$, $\tsp<0$: The car is moving backwards and turning right (clockwise), along a ``D-shaped'' arc of circle.

\item $\msp=0$, $\tsp=-1$: The car is turning right without moving.

\item $\msp>0$, $\tsp<0$: The car is moving forwards and turning right, along a ``C-shaped'' arc of circle.

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

 \subsection{\Sbsec{\Sec1.1}. Germs}

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.

 \subsection{\Sbsec{\Sec1.2}. Counting germs}

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

\item $\pm 1$ if $\cu alpha=\pm\cu \gamma$, and $\ba \gamma$ occurs on the arc but is not an endstate\foot\dag{In this paper, any sentence that uses the symbols $\pm$ and $\mp$ should be read as two separate sentences, one in which $\pm$ is replaced by $+$ and $\mp$ by $-$, and one in which $\pm$ is $-$ and $\mp$ is $+$.};

\item $\pm {1\over2}$ if $\cu alpha=\pm\cu \gamma$, and $\ba \gamma$  is an endstate of the arc;

\item $0$ otherwise.

\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.
   
 \section{\Sec2. Winding numbers and related concepts}

 \section{\Sec3. Convolution}

% Begin

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

\item $\di\gamma=\di\sigma=\di\rho$,

\item $\po\gamma=\po\sigma+\po\rho$,

\item $\cu\gamma = [\tsp(\sigma)\tsp(\rho), \msp(\sigma)\tsp(\rho)+\tsp(\sigma)\msp(\rho)]$. 

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

 \section{\Sec3. Duality}

% Begin

 \section{\Sec9. Ramblings on extension to curved tracings}

% Begin

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  

It seems we do not need negative multiplicities in this metaphor, so $\kappa(s)$ imay be taken to be nonnegative. A slight problem is that now forward and backward moves do not cancel each other automatically; we have to say that a null tracing is one in which $\kappa(s)=-\kappa(\neg s)$ for all $s$. Winding numbers can be defined without major problems (just ignore all states with zero radius of curvature), and same for degrees.

The status of the driving wheel/gearbox can be represented by a parameter $\alpha$ such that $\alpha=0$ is pure forward moving, $\alpha=\pi/2$ is pure left turning, $\alpha=\pi$ is pure backwards moving, and $\alpha=3\pi/2$ is pure right turning; in general, $\cot \alpha$ is the radius of curvature. If we define $\cs (s)=\cos\alpha$ and $\ss (s)=\sin\alpha$, then the dual $s^\ast$ of a state $s$ has position $(\ta s)^\ast$, tangent $(\po s)^\ast$, $\cs (s^\ast)=\ss(s)$, and $\ss(s^\ast)=\cs(s)$. {\bf Or is it $-\cs(s)$?}.

This complication is required only to adapt that part of the theory based on the $\mu$ and $\tau$ counting functions. This may be an overkill; perhaps it is best to define states as usual, define a tracing as a multiset of legs (both forwards and backwards, with positive multiplicities), give an ad hoc definition of null and equivalen tracings, and define all operations by defining their effect on leg pairs and extending them via bilinearity. This requires treating separately all cases of {move, turn, arc}$\times${move, turn, arc} wit the subcases of arc-arc depending on the two radii. It also requires explicit discussion of the rules of the road.

{\bf What a mess! where do we go from here?}

\par\vfill\eject

Κ¬˜Jš
œ>˜>Jš
œE˜E
procš
œ˜Kš
œ:˜:Kš
œ6˜6Kš
œ˜Kš
œ˜—š
œ˜Kš
œ˜Kš
œ˜—š
œ˜˜KšœNΟfœœ;˜Ώ
Kš
œH˜H——š
œ%˜%š
œ2˜2Kš
œΛ
˜Λ
Kš
œ˜Kš
œΆ˜ΆKš
œ’˜’Kš
Ϭ
˜¨
Kš
ϩ
˜©
Kš
œϊ
˜ϊ
Kš
œΜ
˜Μ
Kš
œΣ˜Σ˜
Kš
œI˜IKš
œΆ
˜Ά
Kš
œ:˜:Kš
œl˜lKš
œK˜KKš
œy˜yKš
œD˜DKš
œl˜l—Kš
œ
˜
Kš
œ|˜|—š
œ&˜&Kš
œ£˜£Kš
œ»˜»—š
œ/˜/Kš
œζ˜ζš
œ
˜
Kš
œΕ˜ΕKš
œa˜aKš
œ˜—Kš
œ
˜
Kš
œε˜εKš
œι
˜ι
Kš
œC˜CKš
œ¦˜¦K˜X——Kš
œ8˜8š
œ˜š
œ˜Kš
œΆ
˜Ά
š
œ
˜
Kš
œ%˜%Kš
œ%˜%Kš
œ^˜^—Kš
œ
˜
Kš
œ
˜
Kš
œφ
˜φ
Kš
œό˜ό——š
œ˜Kš
œ˜—š
œ=˜=š
œ˜Kš
œΑ
˜Α
Kš
œύ˜ύKš
œͺ˜ͺKš
œά˜άKš
œ·˜·Kš
œ‡˜‡Kš
œΘ
˜Θ
Kš
œς˜ςKš
œ¬˜¬Kš
œΡ˜ΡJš
œ²˜²Jš
œ˜Jš
œ˜Jš
œ-˜-——Kš
œ˜—…—:Ά=h