\section{1. Introduction}
\subsection{1.1. States and tracings}
A plane curve is usually defined as the trajectory of a pointlike particle whose position $p(t)$ is a smooth function of a ``time'' parameter $t$. The tangent to the curve at a given point $p(t)$ can be defined as the line through that point whose direction is parallel to the particle's velocity vector $p\pr(t)$. Unfortunately, if $p\pr(t)=0$, any line through $p(t)$ satisfies this condition. The common expedient of assuming $p\pr(t)$ to be nonzero excludes all curves having corners or cusps, like polygons and cubic splines, and for that reason it is of limited value in computational geometry. The other two trivial alternatives, accepting either all or none of the lines through $p(t)$ as tangents, are also insatisfactory. Consider for example the problem of determining a line tangent to a polygon $P$ and passing through an exterior point $q$ (figure \bug.1): in most contexts, we would consider $\lscr1$ or $\lscr2$, but not $\lscr3$, as being valid answers.
This paper presents a new framework for the description of plane curves, based on the motions of objects that have both {\it position} and {\it orientation}. Such an object can be imagined as a tiny car, whose {\it state} at any given moment consists of a point of the plane (its current position) and a unit vector (the direction in which its hood is facing). A curve is represented by the sequence of all the {\em states} (not just the points) assumed by the car during some trip on the plane. We consider only motions where the position and orientation of the object change smoothly with time, and where the instantaneous velocity is always colinear with the orientation vector. In other words, the car may move either forwards or backwards, but it may not jump or skid sideways. To distinguish such structures from classical curves and polygons, we call them {\it tracings}.
Note 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, corresponding to intervals during which the car turns upon itself at a fixed point, or reverses its velocity, or both. It is worth emphasizing that the direction in which the car faces and the direction in which it moves are two distinct concepts. Far from being a nuisance, this distinction is essential for the functioning of the entire framework. In particular, there are four distinct ways the car can traverse a given circular trajectory exactly once, without stopping: it may progress either clockwise or counterclockwise, and in each case it may be moving forwards (when its orientation agrees with the direction of motion) or backwards (when the two are opposite). Each of these four possibilities determines a different tracing. See figure \bug.2. Note that trips (a) and (b) have no states in common, whereas (a) and (d) consist of the same states traversed in two different orders. In the same spirit, we distinguish between the tracings defined by two cars that traverse the same path in precisely the same way, except that at some corner of the path one of the cars turns left by $\alpha$ degrees, while the other turns right by $360-\alpha$ degrees. See figure \bug3. In figures like this one, the direction of motion is indicated by hollow arrowheads ($\scriptstyle >$), and the orientation of the car by solid ones ($\rpoint$).
\par\vfill\eject
\subsection{1.2. Applications of the kinetic framework}
These seemingly minor technical differences between tracings and classical curves have surprising and far-reaching consequences, as we will see in the following sections. They enable us to define several important concepts, some familiar from differential topology, but others apparently new. These include the notions of winding number, degree, sweep number, and crossing number of a tracing. We will also be able to rigorously define several operations on tracings, such as additon, multiplication and convolution. The distinction betweention orientation andtion thetion direction oftion motion istion crucialtion fortion thetion propertion definition oftion thesetion operationstion. Several theorems of geometry can be proved by purely algebraic manipulations in the calculus of these tracing operations. 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.
This kinetic approach allows us to recast many proofs and algorithms of computational geometry in a more elegant language. Some examples are computing the convex hull of a simple polygon [\GrY], computing the common tangents or the intersection of two convex polygons, and so forth. In all these cases the kinetic framework improves the simplicity and readability of the algorithm, without affecting their asymptotic time bounds. In a way, the framework imparts geometry with a calculational flavor, in that what were proofs before now become computations. Furthermore, the kinetic approach has already led to a number of new algorithms that improve on previously known bounds. For example, one algorithm computes in logarithmic time the distance between two convex polygons (in any $Lp$ metric), while another tests in linear time whether two convex polygons can disjointly fit into a third one (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. This duality establishes a one-to-one map from tracings to tracings, which interchanges the roles of position and orientation. In particular, straight line segments become corners, and vice-versa. Because of this exact duality, each algorithm solves two problems at once. 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.
The kinetic framework shows potential for significant applications in many practical areas. For example, the convolution of two tracings provides the link between the brush-and-trajectory metaphor for the design of characters and other graphical shapes, as used in Knuth's Metafont program [\Kn], and the filled-outline paradigm used at PARC \note{Reference?}. Another promising application of convolution is design rule checking in VLSI. Its higher-dimensional counterparts are relevant to collision avoidance computations in robotics. 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.
The kinetic approach applies to arbitrary $C^\infty$ curves, and indeed can be extended to handle $C^\infty$ manifolds in arbitrary dimensions. We will limit the more formal treatment to the subclass of {\it polygonal tracings}, or generalized polygons, in which at every instant the car is either moving in a straight line or turning upon a fixed spot. Due to lack of space, most of the proofs will be relegated to the full version of this paper. The general theory, its particularization to other interesting subclasses of tracings (such as concatenations of circular arcs, polyhedra), and most of the applications mentioned above will be reported elsewhere.
\par\vfill\eject
\subsection{1.3. Related work}
The idea of convolution is akin to what is known as the {\it Minkowski sum} of two sets. The sum of two convex sets, in this sense, was used by Schwartz [\Sch] to develop an $O(\lg^2n)$ algorithm for detecting convex polygon intersection. The notion of a pairing of states with matching orientations, which is the fiber product used in the definition of convolution, is an instance of what control theorists call Pontrjagin's principle of maximality [\IK]. Many of the issues in computing convolutions were illuminated by studying the ``mountaineer's problem'' [\Fi]. The convolution of convex objects has been considered in robotics, under the name of ``configuration space approach'', as a tool for collision avoidance computations. See [\TLP]. For convex polygons the connection between Minkowski sums and convolution was also noticed by Toussaint [\Tou]. An informal duality has previously been used several times as a tool in the development of geometric algorithms: examples are [\PM, \EMP]. Finally, the reader can find a formal definition of fiber products in Lang [\La] and an introduction to the appropriate concepts from differential topology (winding number, degree) in [\GP].
\par\vfill\eject
\section{2. Further definitions and notation}
% Begin
\subsection{2.1. Moves, turns, and polygonal tracings}
A {\it move} is a trip in which the orientation of the car remains fixed while its position moves (in a consistent direction) along a straight line segment. A {\it turn} is a trip during which the position of the car stays fixed while it turns upon itself (in a consistent direction) 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).
The position and orientation of a state $s$ will be denoted by $\po s$ and $\di s$, respectively. The {\it opposite} of $s$ is the state $\op s$ having the same position but the opposite orientation. 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.
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. A {\it polygonal trip} is the concatenation of a finite number of moves and turns. If the final state agrees (in position and orientation) with the initial one, the trip is called a {\it tour}. 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 (apart from the choice of starting point) exactly two distinct tours, with opposite orientations and directions of traversal.
\subsection{2.1. Tangents}
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 ($\rpoint$). 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. We say that two lines are parallel if they are parallel in the classical sense and similarly oriented.
The opposite $\op \lscr$ of an oriented line $\lscr$ is defined in the obvious way. The {\it tangent} $\tan s$ of a state $s$ is the line passing through the point $\po s$ and having orientation $\di s$. Note that the motion of the car is not relevant for this definition. The tangent is therefore uniquely defined at every instant along a car trip, even when the velocity of the car is zero.
There may be more than one tangent line passing through a given point on a tracing, or even infinitely many of them; this is always the case at corners, for example. However, not every line passing through a corner is a tangent, but only the ones which were parallel to the car at some instant while it was turning at that corner. For example, consider a car trip around the polygon $P$ of figure \bug.1, with the car moving forwards in the counterclockwise direction and turning left by less than $180\deg$ at each corner. The only tangents to the tracing that pass through the point $q$ will be precisely $\lscr1$ and $\lscr2$ (with the appropriate orientations).
\subsection{3.3. From trips to tracings}
The definition tracings given in section 1 is informal and incomplete. Even if we ignore the timing details, the sequence of states traversed by the car in general 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. We also do not want two forward moves through the same states to cancel out, or to be equivalent to a single move through htose states. Analogous statements should apply to the 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.
\note{Winding numbers section:}
{\small
If $r,s$ are two states with $\ta r=\ta s$, then for any partial tracing we have
$$\mu(s)-\mu(r)=\sum{z\in\la r\sp s\ra}\biglp \mu\xp(z)-\mu\xm(z)\bigrp.$$
Analogous equations hold for the functions $\mu\xp$ and $\mu\xm$, that is,
$$\mu\xp(s)-\mu\xp(r)=\sum{z\in(r\sp s]}\biglp \mu\xp(z)-\mu\xm(z)\bigrp$$
and so forth. Similarly, if $\po r=\po s$, then
$$\tau(s)-\tau(r)=\sum{z\in\la r\sp s\ra}\biglp \tau\xp(z)-\tau\xm(z)\bigrp.$$
For {\em balanced} partial tracings we then have
$$\mu(s)-\mu(r)=-\sum{z\in\la r\sp s\ra}\biglp \tau\xp(z)-\tau\xm(z)\bigrp$$
if $\ta r=\ta s$, and
$$\tau(s)-\tau(r)=-\sum{t\in\la r\sp s\ra}\biglp \mu\xp(z)-\mu\xm(z)\bigrp$$
if $\po r=\po s$. It follows that
$$\sum{\scrp\po z=\po s}\tau\xp(z)=\sum{\scrp\po z=\po s}\tau\xm(z)=\sum{\scrp\po z=\po s}\tau(z)$$
and
$$\sum{\ta z=\ta s}\mu\xp(z)=\sum{\ta z=\ta s}\mu\xm(z)=\sum{\ta z=\ta s}\mu(z)$$
} % end of \small subsection
\note{Ibidem:}
{\small
We may also count in the same way how many times the tracing $A$ crosses the {\it ray into $s$}, which is denoted by $(\infty\sp s\ra$ and consists of all states with tangent $\ta s$ and positioned behind $s$. From the above formula we see that this total is the same as $-\wiA(\op s)$. So we have
$$\sum{\ta r=\ta s}\;\;\; \sum{z\in\laa r\sp \op s\raa} \muA(z)\;\;\; =\;\;\; -\wiA(\op s)+\wiA(s).$$
But $\wiA(\op s)$ is equal to $\wiA(s)$ by lemma 3.1. We conclude that
$$\sum{\ta r=\ta s}\;\;\; \sum{z\in\la r\sp \op r\ra} \muA(z) \;\;\;-\;\;\; \sum{\ta r=\ta s} \;\;\;\sum{z\in\la \op r\sp r\ra} \muA(z) = 0,$$
That is, a balanced tracing $A$ crosses a line $\ta s$ from right to left as many times as it does from left to right.
} % end \small
\note{Further on:}
\subsection{3.7. Convexity}
One of the most attractive features of the new framework is that one can give a novel treatment of the concept of convexity that seems to have, from the algorithmic point of view, several advantages over the classical treatment.
\definition{3.2}{A polygonal tracing $P$ will be called {\it convex} if
\itemno{(a)} all moves are forwards, and
\itemno{(b)} the car faces exactly once in each direction.}
From this definition it is possible to prove a large number of conclusions, including:
\item the tracing is simple (has no self-intersections)
\item tangents are supporting lines
\item all turns are left, or all turns are right
\item the car never faces twice towards the same point
\item $\dg(P) = \pm1$
\item the locations of the car define a convex polygon.
\note{Further on:}
\subsection{4.2. Affine maps and orientation reversals}
Let $M$ be an affine map [\Cox] of the plane into itself; we denote by $P^M$ the image of a point (or set of points) $P$ under $M$. An one-to-one affine map $M$ takes any straight line to another straight line. We define the image of a state $s$ under $M$ as the state $s^M$ with position ${\po s}^M$ and tangent line ${\ta s}^M$. Note that an affine map of negative determinant reverses the orientation of the car. This definition extends naturally to trips, moves, turns, and tracings. Compositions of affine maps are affine. If $M$ and $M\pr$ denote two such maps, then the result of applying first $M$ and then $M\pr$ to tracing $P$ will be denoted by $P^{M\,M\pr}$.
Two particular affine maps we will need further on are translation by a vector $v$ (denoted by $P^{\transl v}$) and $180\deg$ rotation around the origin ($P^\N$). For example, $P^{\N\,\transl x}$ denotes the tracing $P$ rotated by $180\deg$ and then translated by the vector $x$.
\subsection{4.3. Convolution}
The convolution of two subsets $X$ and $Y$ of the Cartesian plane $\reals^2$ is defined as
$$X\ast Y=\rset{x+b\relv x\in X \and y\in Y}.\eqno(1)$$
See figure 2.1. The convolution can be interpreted in many ways. One possibility is given by the equation below:
$$X\ast Y=\union{x\in X} Y^{\transl x},\eqno(2)$$
i.e., the union of copies of $Y$ translated by every element of $X$. Thus if $X$ is a curve and $Y$ a solid paint-brush, $X\ast Y$ denotes the points of the plane that will be colored as the brush $Y$ is swept along the trajectory $X$. Equation (2) can be rewritten as
$$z\in X\ast Y \rmiff (\exists x\in \reals^2)\ x\in X \and z-x\in Y, \eqno(3)$$
or, if $fX$ denotes the characteristic predicate of the set $X$,
$$f{X\ast Y}(z)=\join{x\in \reals^2} fA(x)\and fB(z-x).\eqno(4)$$
The similarity of this last expression with the classical convolution of two real-valued functions $f$ and $g$, namely
$$f\ast g\,(z)=\int{\reals^2} f(x)g(z-x) dx,$$
justifies the name given to the operation $X\ast Y$.
Our goal in this section will be to redefine this operation in the kinetic framework. We can wiew a tracing as the outline of a planar figure, for example by considering all points of the plane with nonzero winding number with respect to the tracing. It is then quite natural to consider the problem of computing a tracing $A\ast B$ representing $X\ast Y$ from two tracings $A$ and $B$ represnting the sets $X$ and $Y$. 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 $X$, $Y$ and $X\ast Y$ at the points $x$, $y$ and $z=x+y$, respectively, must be parallel to each other.}. See fig. 2.3. Why this must be so is clear from that figure. Imagine that $x$ and $y$ move back and forth along the respective boundaries by an infinitesimal amount: if the tangents at those points were not parallel, the sum $x+y$ would completely cover a non-degenerate parallelogram enclosing the point $z$, contradicting the assumption that $z$ is on the boundary.
The {\it convolution $A\ast B$ of two tracings} $A$ and $B$ will be defined essentially by following this basic rule: we take all pairs $a, b$ of parallel states, one from $A$ and one from $B$, and for every such pair we put in the convolution a ``sum'' state $a+b$, whose orientation is the common orientation of $a$ and $b$ and whose position is the vector sum of $\po a$ and $\po b$.
The multiplicities of the states are taken into account in the pairing process. Thus, if $a$ occurs $k$ times in $A$ and $b$ occurs $\lscr$ times in $B$, then we must consider the pair $a,b$ as occurring a total of $k\lscr$ times, each contributing one copy of the sum state $a+b$ to the tracing $A\ast B$.
\note{Further on:}
\subsection{4.5. Product}
It is easy to check that the winding number function $\wi$ is {\it additive} (or {\it linear}) with respect to the second argument; that is, for any point $p$ and any tracings $A, B$, we have $\wi(p, A+B)=\wi(p, A)+\wi(p,B)$. This property is so important that it can almost be regarded as the ``definition'' of the tracing $A+B$. From this point of view, it is natural to ask whether we can define the {\it product} $A\cdot B$ of two tracings $A$ and $B$, with the property that $\wi(p, A\cdot B)=\wi(p, A)\wi(p, B)$. Surprisingly, the answer is ``yes''.
The overall process can perhaps be better undestood by the following description. We break every move of $A$ in two or more consecutive moves, at every point where it crosses the path of $B$. In the same way, we break every move of $B$ at the points where it crosses $A$. After this is done, all points of a given move $m$ of $A$ have the same winding number with respect to $B$, denoted by $\wi(m, B)$; similarly, all points of a given move $n$ of $B$ have the same winding number $\wi(n, A)$ with respect to $A$. The product tracing is constructed then by taking $\wi(m, B)$ copies of every move $m$ of $A$, and $\wi(n, A)$ copies of every move $n$ of $B$. Every turn of $A$ and $B$ is handled in the same way, according to the winding number of its vertex with respect to the other tracing. See figure 4.8. Note that the orientations of the moves do not affect the winding numbers; also, every move or turn that is copied into the product retains its original orientation.
At a point where the two tracings cross, the above rules will result in unbalanced states, some with an excess of incoming moves and some with an excess of outgoing ones. We restore the balance at those points by adding extra turns. By convention, every such turn is less than $180\deg$ (in either direction), and connects an incoming move derived from $A$ to an outgoing move derived from $B$, or vice-versa. This turn will bound the regions of highest winding mumber for the two tracings at that vertex.
\note{Further on:}
Even for oppositely oriented convex tracings multiplication has nice properties. The following result, illustrated in fig. 4.9, will be useful later on:
\lemma{4.8}{If $P$ and $Q$ are two oppositely oriented intersecting convex tracings, and $i$ is the number of their edge intersections, then $\dg(P\cdot Q) = i/2-1$.}
\subsection{4.6. Other operations}
Both the convolution and the product operations can be defined within a generic framework of matching states of two tracings according to a certain criterion, with each matched pair contributing a result state (or states) depending on the pair. A pairing of this sort is called a {\it fiber product}. Many other interesting operations on tracings can be defined this way. For example, one can define the {\it dual product} $A\dpr B$ of two tracings $A$ and $B$, which has the property that $\dg(\lscr, A\dpr B)=\dg(\lscr, A)\dg(\lscr, B)$ for every line $\lscr$ taht is not a common tangent of $A$ and $B$. This operation generalizes the notion of convex hull, in the same way that $A\cdot B$ generalizes the notion of intersection of figures. A fiber product pairing states where the car on $A$ faces the car on $B$ is useful in developing algorithms for computing the intersection of convex polygons and the convex hull of a simple polygon. Due to lack of space we cannot discuss these developments here.