% KineticGarbage.tex of September 7, 1983 7:40 am --- Stolfi

September 1, 1983 9:42 pm

\NEW For example, $\la u\sp \stopp u\ra$ and $\la\stopp u\sp u\ra$ denote two counterclockwise $180\deg$ turns, respectively starting from and ending at the state $u$.

\NEW be the multiset where the states he {\em forward} move or {\em left} turn that begins with the state $u$ and ends with the state $v$ will be denoted by $[u\sp v)$. This also denotes the set of all states assumed by the car during that move or turn, including $u$ but not $v$\foot\dag{\note{Ugly. Symmetry would require using $1\over2$ multiplicities for the endstates. For example, this would make the definition of $\mu$ and $\tau$ more straightforward. Also, define the opposite of a tracing as the one obtained by flipping the black arrows of all states; with the $1\over 2$ convention, the opposite of a move is a move, and the opposite of a turn is a turn, without any caveats about the endstates. Unfortunately, defining moves as $\la u \sp v \ra$ from the outset seems hard to justify in such a small space.}}.

\NEW With these conventions, a partial tracing can be considered as a multiset of {\em states}, resulting from the additive union of its moves and turns. It turns out that {\em two tracings are equivalent if and only if they are the same multiset of states}. Note in particular that the additive union $[u\sp v)+[v\sp w)$ of two concatenable moves $[u\sp v)$ and $[v\sp w)$ is precisely the move $[u\sp w)$. Note also that a forward and a backward move through the same states exactly cancel each other.

\NEW Of particular importance will be the multisets of the form $\la u\sp b\ra=(u\sp v) +{1\over2}\set{u} +{1\over2}\set{v}$, which include each end state with multiplicity $1\over2$.

September 2, 1983 3:27 am

A {\it turn} is a trip during which the car maintains a constant position while smoothly changing its orientation by less than \OLD $180\deg$

\OLD We will denote a move or turn beginning at the state $a$ and ending at the state $b$ by the symbol $(a\to b)$. The states $a$ and $b$ are called the {\it critical} states of $(a\to b)$. The time reversal of $(a\to b)$ is the move or turn $(b\to a)$.

\OLD We can eliminate the over-specific information present in trips as follows.

\OLD

\definition{3.1}{A {\it partial polygonal tracing} is a multiset of moves and turns, subject to the following caveats: We count a backward move as being a negative copy of the corresponding forward move, and similarly for turns. That is, the multiplicity of each move or turn is a {\it signed} integer, under the convention that $-k$ copies of an element are the same as $k$ copies of its time reversal. In addition, if a move $(a\to c)$ is the concatenation of the moves $(a\to b)$ and $(b\to c)$, then one instance of the former is equivalent to one instance of each of the latter. Turns can be decomposed similarly.}

\OLD Any polygonal trip gives rise to a partial polygonal tracing in an obvious way. If the trip is actually a tour, then the resulting partial tracing satisfies a balance condition: each state is entered by a move or turn just as often as it is left by other moves or turns. We will call a partial tracing simply a {\it tracing} when this balance condition is satisfied. Given a tracing, we can attempt to concatenate its moves and turns back into sequences, so as to reconstruct a corresponding tour. In general, there will be more than one way to do this. During this process, we may find that we have formed more than one closed tour. If so, we can choose one point on each tour, and add to the tracing a path from one of these points to the other, and also add the time reversal of that path; this technique allows us to splice two tours into one. Eventually, by a process analogous to finding an Eulerian path in a graph, we can reconstruct a tour from any tracing. In fact, we could have chosen to define a tracing as an equivalence class of tours.

\subsection{4.1 Addition}

\OLD The interpretation of a tracing as a (signed) multiset of moves and turns immediately suggests the idea of the {\it sum} (or multiset union) of two tracings $A$ and $B$, denoted by $A+B$: the multiplicity of a move or turn in $A+B$ is the algebraic sum of its multiplicities in $A$ and in $B$. This addition operation applies to partial tracings as well.

\OLD The {\it null tracing} $Z$, in which every move and turn has multiplicity zero, satisfies $A+Z=Z+A=A$. Taking the time reversal of a tracing $A$ corresponds to inverting the sign of all multiplicities; we denote the resulting tracing by $-A$, and obviously $A+(-A)$ is the null tracing. In general, for any integer $k$ we denote by $kA$ the tracing which is the sum of $k$ copies of $A$ (or $-k$ copies of the time-reversal of $A$).

\subsection{4.2. Affine mappings}

\OLD How to handle oriented lines when the affine map reverses orientation is a fine point left to the full paper.

September 2, 1983 9:43 pm

\OLD The {\it time reversal} of a trip consists of the car going through the same sequence of states in the reverse order. The {\it opposite} of a state $s$ is the state $\stopp s$ with the same position $\stpos s$ but opposite orientation $\stopp{(\sttan s)}$.

\OLD First, we don't want to specify the order in which the various turns and moves occur; we must keep track of the sense of time within each turn or move, but not between them. Moreover, we want two consecutive moves along the same line (with no intervening turn) to be equivalent to a single move passing through the same states, and similarly for turns. Finally, we want a left-to-right move by a car going forward (and hence facing right) to cancel out a right-to-left move over the same path by a car going backward (and hence also facing right). That is, any portion of a trip should cancel out and their time reversals should cancel out. Note that we don't want cars facing right to cancel out cars facing left, no matter how they move.

\NEW From KineMacros.tex:

\def\mup{\mu^{\sss +}}
\def\mum{\mu^{\sss -}}
\def\mupm{\mu^{\sss \pm}}
\def\mump{\mu^{\sss \mp}}
\def\dmu{\Delta\mu}

\def\taup{\tau^{\sss +}}
\def\taum{\tau^{\sss -}}
\def\taupm{\tau^{\sss \pm}}
\def\taump{\tau^{\sss \mp}}
\def\dtau{\Delta\tau}

\def\wip{\omega^{\sss +}}
\def\wi{\omega }
\def\wim{\omega^{\sss -}}
\def\wipm{\omega^{\sss\pm}}
\def\wimp{\omega^{\sss\mp}}

\def\swp{\sigma^{\sss +}}
\def\sw{\sigma }
\def\swm{\sigma^{\sss -}}
\def\swpm{\sigma^{\sss\pm}}
\def\swmp{\sigma^{\sss\mp}}

\def\swp{\sigma^{\sss +}}
\def\sw{\sigma }
\def\swm{\sigma^{\sss -}}
\def\swpm{\sigma^{\sss\pm}}
\def\swmp{\sigma^{\sss\mp}}

\OLD This definition works (and gives a signed integer) as long as the tour does not pass through $p$ itself.

\NEW
{\small

The winding number, sweep number, and degree functions of a partial tracing can be defined algebraically by the formulas below, where $s$ is a state, $p$ a point, and $\lscr$ a line:
$$\eqalign{
w(s)|=\sum
{r\in \la p\sp \infty)}\,\,\,\sum
{{t\in(r\sp \op r)}\atop{\ -(\op r \sp r)}} \mu(t)\,\,\, + \,\,\, {{\tau(s)+\tau(\op s)}\over 2}\cr\vc
s(p)|=\sum
r \,\,\biglp p\in(r \sp \infty)\bigrp\cdot \tau(r)\cr\vc
\delta(\lscr)|=\sum
{\di r=\di \lscr}\,\,(\po r \leftof \lscr)\cdot \tau(r)\cr}$$
If the tracing is balanced, the winding number can be shown to be a function of $\po s$ alone, independent of $\di s$. This definition applies even if the tracing passes through $\po s$. Note that a tracing consisting of a full $360\deg$ left turn at a point $p$ has winding number 1 at $p$ itself, and 0 everywhere else. \note{Elaborate on these remarks in the main text?} \note{The assymetry in the expressions for $w$ and $\delta$ disappears for the 2SP.}

} % end \small

\OLD In view of the above definition it is clear that a convex tracing is completely specified by the underlying polygon and two additional bits of information, one giving the direction of traversal and another the orientation of the car.

\OLD For now we will assume that $A$ and $B$ are {\it transverse}, i.e., that no move of $A$ is parallel to a move of $B$. Therefore, we have only to consider the cases of

\OLD Actually the construction above works also for the case of non-transverse tracings, provided we assign the multiplicities of critical states in the right way. Again, space considerations force us to defer the details to the full paper. There we also prove that the convolution of two tracings $A\ast B$ is unique (that is, it does not depend on the particular decompositions of $A$ and $B$ into moves and turns) and satisfies the balance condition (so that $A\ast B$ is a tracing rather than just a partial tracing). An example of the convolution of two tracings is shown in fig. 4.3.

\OLD Therefore, if we know how to multiply isolated moves and turns, we can compute the product of general tracings by decomposing each into the sum of its elements.

\OLD Instead of pairing states with the same orientation, for the product we will match those having the same $y$-coordinate. Let $r, s$ be a pair of such states, one from each tracing, and assume $r$ is to the left of (has smaller $x$-coordinate than) $s$. For every such pair we add to the product tracing one copy of $r$, with a multiplicity that depends on the direction in which $s$ was traversed. Specifically, if the car passed through $s$ while moving up, we take one copy of $r$; if the car was moving down at $s$, we take minus one copy of $r$. If the car at $s$ was turning or moving horizontally, we take zero copies of $r$ (in other words, we ignore that pair altogether). In the special case when $r$ and $s$ have the same position (so neither is to the left to the other), we will add to the product the entire turn whose extreme states are $r$ and $s$ (see figure 4.6). We take the left turn if both states are traversed forwards, or both backwards; otherwise we take the right turn. This rule is ambiguous if $r$ and $s$ face in opposite directions, a problem that will be handled in the full paper.

As in the convolution, if $a$ is traversed $k$ times by $A$, and $b$ is traversed $\lscr$ times by $B$, we must consider the pair $a, b$ as occuring $k\lscr$ times, and add its contribution that many times to the product tracing. The usual sign rules apply here too: passing through a state while turning right or moving backwards counts as minus one occurrence of that state.

By applying the pairing rule, we can see that the product of two turns (at different positions) is null. If $m$ is a forward move that is not horizontal, and $t$ is a left turn that lies in the ``left shadow'' of $m$, then their product will be $t$ if $m$ goes up, and $-t$ if $m$ goes down. Otherwise, the product will be null. The product of two moves $m
1$ and $m
2$ may be either null, a single move, or two moves and a turn, depending on their relative positions. Figure 4.7 illustrates the various possibilities. The full paper contains a precise description of these rules, including the handling of degenerate cases.

\NEW {\small

For the precise definition of product, we need first define for a state $s$ the ``displaced winding numbers'' $w^{+}(s)$ and $w^{-}(s)$, that give the values of $w(p)$ for a point $p$ respectively just ahead and just behind the state $s$. These are given by the formulas
$$w^{+}(s)=\sum
{r\in (s\sp \infty)}\,\,\,
\sum
{{t\in\la r\sp \op r\ra}\atop{\ -\la\stopp r\sp r\ra}} \mu(r)$$
and
$$w^{-}(s)=\sum
{r\in [s\sp \infty)}\,\,\,
\sum
{{t\in\la r\sp \op r\ra}\atop{\ -\la\stopp r\sp r\ra}} \mu(r).$$

The state counting functions for the product are then defined by
$$\eqalign{
\mu\xp
{A\cdot B}(s)|=\mu\xp
A(s)w^{+}
B(s) + \mu\xp
B(s)w^{+}
A(s)\cr\vc
\mu\xm
{A\cdot B}(s)|=\mu\xm
A(s)w^{-}
B(s) + \mu\xm
B(s)w^{-}
A(s)\cr\vc
\tau\xp
{A\cdot B}(s)|=\tau\xp
A(s)w
B(s)+\tau\xp
B(s)w
A(s)
-\tau\xp
A(s)\tau\xp
B(s)\cr\va
\null|\hskip10pt +\sum
{x\in (\op s\sp s]}\,\,\,
\sum
{y\in (s \sp \op x)}
\biglp P
{A,B}(x,y)+P
{B,A}(x,y)\bigrp\cr\vc
\tau\xm
{A\cdot B}(s)|=\tau\xm
A(s)w
B(s)+\tau\xm
B(s)w
A(s)
-\tau\xm
A(s)\tau\xm
B(s)\cr\va
\null|\hskip10pt +\sum
{x\in (\op s\sp s)}\,\,\,
\sum
{y\in [s \sp \op x)}
\biglp P
{A,B}(x,y)+P
{B,A}(x,y)\bigrp\cr
}$$
where
$$P
{A,B}(x,y)={{\mu\xp
A(x)\mu\xm
B(y)+\mu\xm
A(x)\mu\xp
B(y)}\over 2}.$$

These formulas apply to any partial tracings $A$ and $B$. However, the product of two {\em tracings} $A$ and $B$ is a tracing only if $A$ and $B$ have no oppositely oreinted moves with coincident positions. If this does happen, the product will be balanced but may contain moves and turns with half-integer multiplicities.

} % end of \small


\OLD Note that if we think of $A$ and $B$ as fixed and $x$ as variable, then both sides are defined, except for a set of points $x$ of measure zero. In the full paper we will see that both sides of the equation are undefined for exactly the same values of $x$.

September 7, 1983 12:44 am

\OLD We present a new framework for geometric computing in which planar curves are formed by the motions of objects that have both {\it position} and {\it orientation}. Informally, consider the motion of a car: at each instant the car is positioned at some point in the plane, and oriented with its hood facing in some direction. Together, the position and the orientation specify a {\it state}. In the new framework, curves and polygons are paths in this state space satisfying the constraint that wherever the tangent of the position component of the curve is defined, it must be parallel to the the orientation must be parallel to the either the same as that tangent, or the opposite. In other words, the car may move either forwards or backwards, but it may not skid sideways. To distinguish these structures from classical curves and polygons, we call them {\it tracings}. Several important concepts can be defined for tracings, some familiar from differential topology, but others apparently new. These include the notions of winding number, degree, and sweep number. A general construction, known as {\it fiber product}, is used to define various operations on tracings, including convolution and multiplication. Each fiber product involves forming all pairs of states, one from each tracing, that satisfy a certain constraint.

Using these ideas, it is possible to recast large parts of computational geometry, such as convexity, in a new and advantageous light. This applies to proofs of theorems, as well as to descriptions of algorithms. Besides allowing us to recast old material, this kinetic approach has also led to a number of new algorithms that improve on the previously known bounds. For example, one algorithm computes the distance between two convex polygons in logarithmic time, while another tests if two convex polygons can disjointly fit into a third one in linear time (no rotations allowed). A final attraction of the kinetic approach is that, after appropriately extending the plane into a new manifold, the {\it two-sided} plane, we can define a formal duality between points and lines that maintains the sense of left and right. Informal notions of such a duality had previously been used in computational geometry, but now for the first time we can say in a precise sense that, for example, an algorithm for computing the convex hull of $n$ points is also an algorithm for computing the intersection of $n$ half-planes.

It may be of interest to note that the origins of this approach lie in an effort to unify Metafont-style [\Kn] graphical shape descriptions, based on a brush-trajectory metaphor, with those used at PARC, based on outlines.

\subsection{1.1. Further results}

We now proceed to mention in more detail the developments this framework has led to. An area particularly well illuminated by the framework is convexity. Using the concepts of position and orientation, it is possible to define the notion of convexity in several equivalent new ways. Classical properties of convex figures, such as the existence of separators and common tangents, or properties of special classes, such as center-symmetric figures, can now be derived in a novel fashion. Well-known algorithms, such as the Graham-Yao algorithm [\GrY] for computing the convex hull of a simple polygon, can be understood very simply via an appropriate fiber product. Monotone polygons can also be dealt with nicely.

Using the framework we have obtained new algorithms for many geometric problems, as, for example, computing the extrema in a given direction of a convex polygon, computing the common tangents, detecting or computing the intersection, and computing the distance between two convex polygons (in any $L
p$ metric), etc. In all cases the algorithms we obtain are simple to code and give us asymptotic time bounds equal to or better than what is already known. An instance of improvement is the distance computation mentioned above. Furthermore, we have discovered that many of these algorithms also work for a wider class of tracings than the convex ones, namely the {\it monostrofic} tracings we will introduce later on.

Besides its impact on classical problems, the new framework has given rise to algorithmic problems of its own. The question of how to compute the fundamental operations defined on tracings, such as convolution, product, and dual product, leads to interesting algorithms. And because of the exact duality, each algorithm solves two problems at once. In a way, the framework imparts geometry with a calculational flavor, in that what were proofs before now become computations. It is also worth pointing out that the concepts introduced in this paper can be generalized to define $C^\infty$, as well as polyhedral, tracings in arbitrary dimensions.

Besides pure geometry, the framework shows potential for significant applications in many practical areas, such as the description of graphical shapes in illustration or font-design systems, collision avoidance computations in robotics, and new algorithms for design rule checking in VLSI. The algorithms obtained are simple and, because they are based on intrinsic descriptions of the geometric objects involved, they have good locality properties. For example, no global sorting, as often required in sweep-line algorithms [\Ni], is necessary. Many of the above developments will be reported elsewhere, due to lack of space in this paper. Our emphasis here will be on polygonal tracings in the plane.

\OLD (from section 3.1) It is worth emphasizing that the direction in which the car faces and the direction in which it moves are two distinct concepts. This distinction, far from being a nuisance, is essential for the functioning of the entire framework. In illustrations of tours, we will indicate the direction of motion by hollow arrowheads ($\scriptstyle >$), and the orientation of the car by solid arrowheads ($\rpike$).



\OLD

The next section is not part of the formal development; it is intended to motivate some of the concepts we will introduce.

\section{2. Motivation -- the convolution of two figures}

{\small

The convolution of two subsets $A$ and $B$ of the Cartesian plane $\reals^2$ is defined as
$$A\ast B=\rset{a+b\relv a\in A \and b\in B}.\eqno(1)$$
See figure 2.1. The convolution can be interpreted in many ways: for example, if we denote by $B^{\und a}$ the set $B$ translated by the vector $a$, then clearly
$$A\ast B=\union
{a\in A} B^{\und a},\eqno(2)$$
i.e., the union of copies of $B$ translated by every element of $A$. Thus if $A$ is a curve and $B$ a solid paint-brush, $A\ast B$ denotes the points of the plane that will be colored as the brush $B$ is swept along the trajectory $A$. Equation (2) can be rewritten as
$$x\in A\ast B \rmiff (\exists y\in \reals^2)\ y\in A \and x-y\in B, \eqno(3)$$
or, if $f
X$ denotes the characteristic predicate of the set $X$,
$$f
{A\ast B}(x)=\join
{y\in \reals^2} f
A(y)\and f
B(x-y).\eqno(4)$$
The similarity of this last expression with the classical convolution of two real-valued functions $f$ and $g$, namely
$$f\ast g\,(p)=\int
{\reals^2} f(q)g(p-q) dq,$$
justifies the name given to the operation $A\ast B$.

Another important characterization of $A\ast B$ is given by the following result. Let $A^N$ be the set $A$ rotated $180\deg$ around the origin, i.e. $A^N=\rset{-a\relv a\in A}$. Then from equation (3) we get
$$x\in A\ast B \rmiff A\inte B^{N\,\und x} \neq \empty\eqno(5).$$
That is, the point $x$ is in $A\ast B$ if and only if the set $B$ rotated $180\deg$ and translated by $x$ intersects $A$ (fig. 2.2).

} % end \small

\subsection{2.1. Convolution and the outline representation}

{\small

In computational geometry, a planar figure is commonly specified by a suitable representation of its boundary, or {\it outline}. For example, a simple polygon $P$ is usually represented by a list of its vertices, with the understanding that the edges of $P$ are the segments connecting consecutive vertices. The boundary may also be described by an algebraic or parametric curve, or by a collection of segments of such curves. In view of the wide applicability of this model, it is quite natural to consider the problem of computing the outline of $A\ast B$ from those of $A$ and $B$. It is not hard to see that a point $x$ on the boundary of $A\ast B$ must be the sum of a boundary point $a$ of $A$ with a boundary point $b$ of $B$. But the crucial observation is that {\it the tangents to $A$, $B$ and $A\ast B$ at the points $a$, $b$ and $x=a+b$, respectively, must be parallel to each other.}. See fig. 2.3. Why this must be so is clear from that figure. Imagine that $a$ and $b$ move back and forth along the respective boundaries by an infinitesimal amount: if the tangents at those points were not parallel, the sum $a+b$ would completely cover a non-degenerate parallelogram enclosing the point $x$, contradicting the assumption that $x$ is on the boundary.

This immediately suggests a procedure for computing the outline of $A\ast B$ from those of $A$ and $B$, whose {\it basic rule} is to take all points of the form $a+b$ where $a$ and $b$ lie on the given outlines and have parallel tangents. Unfortunately, this simplistic approach suffers from three major problems:

The first problem is that not all points of an outline have a well-defined tangent. Consider the example of figure 2.4, a square convolved with a circle. The point $x
1$ on the boundary of the convolution has a unique decomposition as $a
1+b
1$ with $a
1\in A$ and $b
1\in B$, but the tangent to $A$ at $a
1$ is not defined.

The second problem arises from an inherent ambiguity in the slope of a tangent line, and is also illustrated by the example of figure 2.4. The tangents to $B$ at the points $b
2$ and $b
2\pr$ have the same slope, which also matches that of the tangent to $A$ at $a
2$. Yet, while $x
2=a
2+b
2$ is a boundary point of $A\ast B$, the point $x
2\pr=a
2+b
2\pr$ is not. We can explain this failure by noticing that the tangents at $a
2$ and $b
2$ touch $A$ and $B$ respectively from above, while the tangent at $b
2\pr$ touches $B$ from below.

The third problem is that the equality of slopes at $a$ and $b$ is only a necessary but not sufficient condition for $a+b$ to lie on the boundary of $A\ast B$. The converse may fail because the point $a+b$ may also be expressible as $a\pr+b\pr$ for two points $a\pr$ of $A$ and $b\pr$ of $B$ which do not satisfy the basic constraint; an example of this situation is depicted in figure 2.5.
Stated another way, the outlines obtained by a straightforward application of the basic rule may be self-intersecting, and therefore some portions of them may be spurious and lie in the interior of the convolution. This problem is more ``global'' in nature than the previous two: the detection and removal of those spurious portions seems to require a nontrivial processing of the resulting outline.

In the following sections we will discuss a generalized outline representation, based on the concept of tracings, which solves these problems in a mathematically clean way. The first problem is solved by requiring the tangent(s) at each point to be explicitly given as part of the outline specification. The second is handled by endowing each tangent with an orientation. And the third one is solved by extending the concepts of boundary and interior so as to accept self-intersecting outlines, and interpreting them in a suitable way. With these extensions, the basic rule becomes both necessary and sufficient.

This discussion summarizes the historical motivation for the concept of tracings as defined below. However, the ability to cleanly support the operation of convolution is only one of the reasons that make tracings worth of further study. Many other important properties, such as the duality principle discussed in section 7, make tracings valuable in the synthesis, description, and verification of geometric algorithms.

} % end \small

\OLD

\section{3. Further definitions and notation}

The goal of this section is to define polygonal tracings and some related concepts. We will begin with informal, and at times incomplete, descriptions for maximum clarity. The formal definitions given in the smaller print are actually be more succint and handle all cases correctly. Due to lack, of space all proofs here and in the following sections are omitted.

\subsection{3.1. States and tours}

By an {\it oriented line} we mean a straight line endowed with an {\it orientation}, one of the two unit vectors parallel to it. From now on, all lines are assumed to be oriented ones, unless stated otherwise. The orientation of a line $r$ will be denoted by $\di r$, and represented it in the illustrations by a solid arrowhead ($\rpike$). The left and right sides (half-planes) of a line $r$ are defined with respect to an observer standing on $r$ and facing in the direction specified by its orientation vector. The {\it opposite} of $r$ is the line $\op r$ having the same position as $r$ but the opposite orientation. We say that two lines are parallel if they are parallel in the classical sense and similarly oriented.

We define a {\it state} $s$ as a pair consisting of a {\it position} $\po s$ (a point in the plane) and a {\it tangent} $\ta s$ (an oriented line containing $\po s$). The {\it orientation} $\di s$ of $s$ is by definition that of its tangent line. Informally, a state describes the position $\po s$ of the car at some instant, and the direction $\di s$ in which it is facing. Note that we distinguish between a state $s$ and its {\it opposite} $\op s$, the state having the same position but the oppositely oriented tangent $\op{(\ta s)}$.

A {\it trip} corresponds to the sequence of all states traversed as the car moves on the plane along some arbitrary trajectory, during some finite time interval. We require this motion to be ``smooth'', i.e., both the position and orientation must be continuous and differentiable functions of time. Furthermore, at every instant when the velocity vector (derivative of the position of the car) is nonzero, it must be collinear with the car's orientation. These restrictions prevent the car from ``jumping'' or ``skidding'', but allow it to remain stationary for nonzero intervals, or to move backwards; see figure 3.1. A {\it tour} is a closed trip, i.e., one whose initial and final states are identical, in position and orientation. The formalization of these concepts is tedious but straightforward.

In illustrations of tours, we will

A trip specifies more than just the curve that is traced by the car, its ``tire tracks'', so to speak; a trip also specifies an oriented tangent line at each point, and a time-ordering of the points. Note that a state may occur several times in a trip, and that the movement of the car has to be smooth as a function of time, not of arc length. Thus, the curve traced by the car may contain corners or cusps. On the other hand, the trip is only the {\it sequence} of states traversed by the car; the speed with which the car passes through these states, or the length of time that it lingers in a given state, are not important.

The concatenation of two trips is defined in the obvious way, provided the final state of the first trip concides, in position and orientation, with the initial state of the second. The {\it null trip} is the empty sequence of states, which can be concatenated with any trip.

\subsection{3.2. Moves, turns, and polygonal trips}

A {\it move} is a trip in which the car maintains a constant orientation while changing its position so as to trace out a straight line segment. A {\it turn} is a trip during which the car maintains a constant position while smoothly changing its orientation by less than $360\deg$. Moves can be either {\it forward} (when the motion of the car agrees with its orientation) or {\it backward} (when the two are opposite). Turns can be either {\it left} (counterclockwise) or {\it right} (clockwise). A {\it polygonal trip} is the concatenation of a finite number of moves and turns. Figure 3.2 shows an example of a polygonal tour. From now on all trips should be assumed to be polygonal unless stated otherwise.

The obvious continuity constraints are implicit in this definition; for example, between two non-collinear moves there must be at least one turn. The positions that the car assumes during a polygonal tour define a (possibly self-intersecting) polygon, with moves corresponding to sides and turns corresponding to vertices. Conversely, from any simple polygon $P$ we can construct a polygonal tour in the following way: each side of $P$ becomes a forward move, and each vertex of $P$ becomes a turn (right or left) by less than $180\deg$. We call the resulting trip a {\it simple polygonal tour}. Such a tour is completely determined by the the vertices of $P$ and their order of occurence. Note that from the same polygon $P$ we can obtain exactly two distinct tours, with opposite orientations and directions of traversal.

The {\em forward} move or {\em left} turn that begins with the state $u$ and ends with the state $v$ will be denoted by $\la u \sp v\ra$. For this definition to make sense, we must have either $\po u = \po v$ (for a turn), or $\ta u = \ta v$ and $\po v$ ahead of $u$ (for a move). The states $u$ and $v$ are called the {\it extremities} of the move or turn.

\subsection{3.3. From trips to tracings}

With the above definition of a trip, we managed to get rid of most of the timing details of the car's movement, and retain only its topological and geometrical content. However, a trip still contains too much information for our purposes. First, we don't want to specify the order in which the various turns and moves occur; we must keep track of the sense of time within each turn or move, but not between them. Moreover, we want two consecutive moves along the same line (with no intervening turn) to be equivalent to a single move passing through the same states. We also want a forward move to be cancelled out by a backward move where the car passes through the same states in the oposite order, but still facing the same way. Note that we don't want moves with the car facing one way to cancel out moves with the car facing the opposite way, no matter how they are traversed. Finally, we want analogous statements to hold for turns.

It turns out that we can eliminate the over-specific information present in a polygonal trip by considering just the {\it multiset of the states traversed by the car}. By definition, the number of times a given state $s$ occurs in this multiset is equal to the number of forward moves and left turns passing through $s$, minus the number of backward moves and right turns passing through $s$. A move that begins or ends at $s$ contributes only $+{1\over2}$ or $-{1\over2}$ to the multiplicity of $s$, depending on whether it is forward or backward, and the same caveat applies to turns. Note that these rules define a {\it signed} multiset, in which some states may have negative (and/or fractional) multiplicities.

In particular, the forward move or left turn $\la u \sp v\ra$ (with $u\neq v$) can be interpreted as a multiset of states, where $u$ and $v$ occur with multiplicity $1\over2$, and all states between them occur with multiplicity one. A backward move or right turn from state $v$ to state $u$ determines a multiset where $v$ and $u$ have multiplicity $-{1\over2}$, and each intermediate state has multiplicity minus one; we will therefore denote such a move or turn by $-\la u\sp v\ra$. Note that the sum (additive multiset union) $\la u\sp v\ra+\la v\sp w\ra$ of two concatenable moves $\la u\sp v\ra$ and $\la v\sp w\ra$ is precisely the move $\la u\sp w\ra$. Note also that the sum of a forward and a backward move through the same states is the empty multiset.

\definition{3.1}{A {\it partial tracing} is a signed multiset of states that can be expressed as the sum of finitely many moves and turns, each taken with arbitrary multiplicity.}

If each move and turn is taken with integer (not necessarily positive) multiplicity, the partial tracing is said to be {\it integral}. Any polygonal trip gives rise to an integral partial tracing in the obvious way. If the trip is actually a tour, then the resulting partial tracing is also {\it balanced\/}: each state is entered by a move or turn just as often as it is left by other moves or turns. The converse also is true: every integral and balanced tracing can be obtained from a tour, by a straightforward adaptation of Euler's graph traversal algorithm. An integral and balanced partial tracing will be called simply a {\it tracing}. The {\it null} tracing is defined to be the one where each state occurs with zero multiplicity.

Clearly, not all multisets of moves and turns are partial tracings. The points of the plane that are then position of some state of a partial tracing (with nonzero multiplicity) is necessarily one-dimensional, except for a finite number of crossings and isolated points. If these points are excluded, what remains is the union of finitely many line segments. Analogous statements apply to the set of all tangent lines.