\input PapNCHdr \input KineMacros

\begfile{KinFOCS1.tex of September 12, 1983 12:58 pm --- Stolfi}

%  Kinetic Framework - Extended abstract for FOCS '83 (part 1 of 3)

\inputtty % your chance to \def\printfilestamp{F}

\paper{A Kinetic Framework for Computational Geometry}
\def\paptitle{Kinetic framework}

\author{Leo Guibas, Lyle Ramshaw, and Jorge Stolfi}
\institution{Xerox PARC and Stanford University}

\vskip-3pt
\hbox par \pagewidth pt{\hfil\it Extended Abstract}
  
\support{The work of Jorge Stolfi, who is on leave from the University of S{\cmr\s\rm a}o Paulo, was partially supported by a grant from Conselho Nacional de Desenvolvimento Cient{\cmr\'\i}fico e Tecnol{\cmr\'\rm o}gico (CNPq).}

\def\dpr{{\raise1pt \hbox{$\scriptstyle \odot$}}}
\def\NEW{{\bf NEW: }}
\def\OLD{{\bf TO DELETE: }}
\def\ENDNEW{{\bf END NEW.}}
\def\ENDOLD{{\bf END DELETE.}}

% reference macros

\def\CD{CD}
\def\Cox{Cox}
\def\EMP{EMP}
\def\Fi{Fi}
\def\GP{GP}
\def\GrY{GrY}
\def\IK{IK}
\def\Kn{Kn}
\def\La{La}
\def\OvL{OvL}
\def\Ni{Ni}
\def\PM{PM}
\def\Sch{Sch}
\def\Sh{Sh}
\def\TLP{TLP}
\def\Tou{Tou}

\def\AA{\hbox{\bf A}}
\def\BB{\hbox{\bf B}}


\section{1. Introduction and summary}

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, the orientation must be 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 {\it 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 (in any $L
p$ metric) between two convex polygons, 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.

\subsection{1.2. 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 [\La] and an introduction to the appropriate concepts from differential topology (winding number, degree) in [\GP].

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↑{\tran a}$ the set $B$ translated by the vector $a$, then clearly
$$A\ast B=\union
{a\in A} B↑{\tran a},\eqno(2)$$
i.e., it is 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\,(x)=\int
{\reals↑2} f(y)g(x-y) dy,$$
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\,\tran 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$ (figure 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}. The boundary may 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 figure 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.1, 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.1. 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 a 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 expressed as $a\pr+b\pr$ for two points $a\pr$ of $A$ and $b\pr$ of $B$ which do not satisfy the basic constraint. 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.

} % end \small


\section{3. Polygonal tracings}

The goal of this section is to define polygonal tracings and some related concepts.  We start with informal, and at times incomplete, descriptions for maximum clarity. The formal definitions given in the smaller print are actually be more succinct 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, unless stated otherwise. The orientation of a line $r$ will be denoted by $\di r$. 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 $\di r$. 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 constitutes an instantaneous description of the position $\po s$ of the car, and the direction $\di s$ in which it is facing.    

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 concatenation of two trips is defined in the obvious way, provided the final state of the first trip coincides, in position and orientation, with the initial state of the second. The formalization of these concepts is tedious but straightforward.

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

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.

\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. 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. If a polygonal trip starts and ends at exactly the same state, it will be called a {\it polygonal tour}. Figure 3.2 shows an example.

Certain 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 occurrence.  

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 extremal states} 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 canceled out by a backward move where the car passes through the same states in the opposite 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 signed 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 multiset sum $\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 polygonal 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, or a collection of tours, 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 is also true: every integral and balanced tracing can be obtained from a tour, by a straightforward adaptation of Euler's graph traversal algorithm\foot\dag{In general, there will be more than one way to do this. During the 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.}. 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.  

\subsection{3.4. State counting functions}

{\small

Let $A$ be a partial tracing, and $s$ an arbitrary state. Let $x$ be a state ahead of $s$ and collinear with it, and consider how the multiplicity of $x$ in $A$ varies as $x$ moves towards $s$ along $\ta s$. Since $A$ is the sum of finitely many moves and turns, this multiplicity will tend to a definite limit $\mu\xp(s)$, which is simply the number of forward moves that exit (or pass through) $s$, minus the backwards moves the enter (or pass through) $s$. Informally, $\mu\xp(s)$ is the net amount of forward movement going on just in front of $s$, that is, through the states with the same tangent line and located just a little bit away from $s$ in the direction $\di s$. In the same way, by letting $x$ approach $s$ from behind we can define $\mu\xm(s)$, the net amount of forward movement that is going on just behind of $s$.

The net amount $\tau\xp(s)$ of left turning going on just to the left of $s$ can similarly be defined by considering a state $x$ with same {\em position} as $s$, and whose orientation forms a vanishing counterclockwise angle with $\di s$. By letting $\di x$ approach $\di s$ from the right we get $\tau\xm(s)$, the net amount of left turning just to the right of $s$. Summarizing, a partial tracing defines four basic {\it state counting functions:} 
$$\eqalign{
 \mu\xp(s)=(\hbox{forward moves out of $s$})
              -(\hbox{backward moves into $s$})\cr
 \mu\xm(s)=(\hbox{forward moves into $s$})
              -(\hbox{backward moves out of $s$})\cr
 \tau\xp(s)=(\hbox{left turns out of $s$})
              -(\hbox{right turns into $s$})\cr
 \tau\xm(s)=(\hbox{left turns into $s$})
              -(\hbox{right turns out of $s$}),\cr}$$
where a move or turn passing through $s$ is considered to be both entering and exiting it. When the partial tracing is not specified by the context, we shall write it as a subscript, as in $\mu\xp
A(s)$, or as a second argument, as in $\mu\xp(s, A)$.

The following quantities are sometimes more convenient to use in algebraic formulas:
$$\mu(s)={{\mu\xp(s)+\mu\xm(s)}\over2},\hskip30pt
\tau(s)={{\tau\xp(s)+\tau\xm(s)}\over2}.$$
       
The quantities $\mu(s)$ and $\tau(s)$ can be interpreted as the net amounts of moving and turning that take place at the point $\po s$ and with the car facing in the direction $\di s$. The multiplicity of $s$ in the partial tracing is precisely $\mu(s)+\tau(s)$. Therefore, the tracing $A$ is completely determined by the four state counting functions $\mu\xp, \mu\xm, \tau\xp$, and $\tau\xm$.
 
A partial tracing is integral if and only if $\mu\xp(s), \mu\xm(s), \tau\xp(s)$, and $\tau\xm(s)$ are integers for all states $s$. Also, a partial tracing is balanced if and only if
$$\mu\xp(s)-\mu\xm(s)\; + \;\tau\xp(s)-\tau\xm(s) = 0$$
for all $s$. Note that for a single state $s$ the numbers $\mu\xp(s)$, $\mu\xp(\op s)$, $\mu\xm(s)$, and $\mu\xm(\op s)$ are four distinct, independent quantities, even for integral and balanced tracings.

In algebraic formulas, we will use the expression $s\in A$ as having a numerical value, which is the multiplicity of the state $s$ in the partial tracing $A$. In a similar vein, we define the numerical value of the predicate ``$p\leftof \lscr$'' to be $+1$ if the point $p$ is to the left of the line $\lscr$, $0$ if $p$ is to the right, and $1\over2$ if $p$ is on $\lscr$. We also define summation ranging over a multiset $A$ by the equation
$$\sum
{s\in A}\,\, f(s) = \sum
s \,\,(s\in A)\cdot f(s).$$

We will use occasionally the symbol $[u \sp v]$ to denote the same multiset as $\la u\sp v\ra$, except that the endstates $u$ and $v$ occur with multiplicity one each, instead of $1\over2$. In the same way we define the variants $[u\sp v)=[u\sp v] - \set{v}$, $(u\sp v]=[u\sp v]-\set{u}$, and $(u\sp v)=[u\sp v]-\set{u}-\set{v}$. Note that when $u=v$ the symbol $[u \sp v]$ denotes the set $\set{u}$, the symbol $(u \sp v)$ denotes $-\set{u}$, and all other variants denote the empty set.

} % end of \small subsection

\subsection{3.5. Winding numbers, sweep numbers, and degree}

Let $A$ be a partial tracing, and $s$ a state. Let us denote by $\la s \sp\infty)$ the {\it ray out of $s$}, the set of all states with tangent $\ta s$ and located ahead of $s$. The {\it winding number of $s$ with respect to $A$} is the total number of moves of $A$ that cross this ray from right to left, minus the number of those that cross it from left to right. We denote this quantity by $\wi(s)$\foot\dag{We will write also $\wi
A(s)$ or $\wi(s, A)$ when $A$ is not clear from the context.}.

{\small

More precisely, $\wi(s)$ is defined by the formula
$$\wi
A(s)=\sum
{r\in \la s\sp\infty)}\;\;\;\sum
{z\in\laa r\sp\op r\raa}\mu
A(z)\;\;\;
  +\;\;\;{{\tau
A(s)+\tau
A(\op s)}\over 2},$$
where $\laa u\sp v\raa$ denotes the multiset $\la u\sp v\ra-\la v\sp u\ra=( u\sp v)-(v\sp u)$. By convention, $s$ has multiplicity $1\over2$ in the multiset $\la s\sp\infty)$, so any moves of $A$ that pass through $\po s$ (and are not collinear with $\ta s$) contribute only $\pm{1\over2}$ to the winding number. Note also that the only turns of $A$ contributing to $\wi(s)$ are those positioned at $\po s$ and spanning $\di s$ or its opposite.

}

Winding numbers have the following property:

\lemma{3.1}{If $A$ is balanced, and $\po r=\po s$, then $\wi
A(r)=\wi
A(s)$.}

That is, $\wi
A(s)$ is independent of $\di s$, and is a property of $\po s$ and $A$ alone (see figure 3.3). Intuitively speaking, $\wi(s)$ counts how many times the car ``winds around'' $s$ while traversing $A$, where we count each complete circuit as $+1$ if counterclockwise, and $-1$ if clockwise (as seen from $s$).

{\small

If $A$ is both integral and balanced, and does not pass through $\po s$, then $\wi
A(s)$ is a (signed) integer. If the tracing passes through $\po s$, the winding number is some integer multiple of $1\over2$. In particular, if $A$ is consists of a simple polygonal tour oriented counterclockwise, $\wi
A(p)$ is zero when $p$ is outside the polygon, $1$ when $p$ is inside it, and $1\over2$ when $p$ is on its boundary. A tracing where the car describes $k$ complete $360\deg$ turns at a point $p$, without any moves, has winding number $k$ at $p$, and $0$ everywhere else.

} % end \small

A related concept is that of the {\it sweep number} of a point $p$ with respect to $A$, denoted by $\sw
A(p)$. This quantity is the signed count of how many times the car faces towards $p$ while traversing $A$, with each time counted as $+1$ or $-1$ depending on whether the car is turning left or right at that instant; see figure 3.4.

{\small

In algebraic terms, the sweep number is defined by
$$\sw
A(p)=\sum
z \;\;\biglp p\online (z\sp\infty)\bigrp\, \tau
A(z).$$

} % end \small

The sweep number is a relativistic variant of the winding number, in the following sense. To an observer traveling with the car and keeping a frame of reference fixed with respect to the car it appears that the point $p$ is moving around some closed trajectory. The winding number of the observer with respect to that trajectory is then equal to $-\sw
A(p)$.
 
The {\it opposite} $\op A$ of a tracing $A$ is obtained by reversing the orientation of all states traversed by the car, while preserving their positions and their time ordering. In particular, every forward move $\la u\sp v\ra$ is replaced by the backward move $-\la \op v\sp\op u\ra$ (from $\op u$ to $\op v$), and every left turn $\la u\sp v\ra$ is replaced by the left turn $\la \op u\sp \op v\ra$. Informally, this corresponds to the car describing the same trajectory, but facing all the time the other way around. It turns out that sweep numbers are not affected by this operation:    

\lemma{3.2}{For a balanced tracing $A$ and any point $p$ we have $\sw(p, A)=\sw(p, \op A)$.}

In other words, the net number of times the car sweeps $p$ with its headlights is the same as the net number of times it sweeps $p$ with its tail lights\foot\dag{Continuing this analogy, imagine that a spotlight attached to the car sends off a beam that makes an arbitrary angle $\alpha$ with the car's axis, and let us count how many times the beam sweeps through the point $p$. We count such occurrences as $+1$ if the car is turning left, or moving with $p$ to the right of its tangent, and as $-1$ in the other cases. No matter what $\alpha$ is, this count will be equal to the sweep number $\sw
A(p)$. The definition above and lemma 3.2 cover the cases $\alpha=0$ and $\alpha=180\deg$, where only the turns of $A$ are relevant.}. Therefore, if all turns of $A$ are in the same sense, the number of tangents to $A$ passing through $p$ is $2\,\leftv \sw
A(p)\rightv$, an observation we will need later on.

A concept dual to winding number (in the precise sense we will see) is that of the {\it degree of a line $\lscr$} with respect to a tracing $A$, denoted by $\dg(\lscr, A)$ or $\dg
A(\lscr)$. This integer counts how many times the car on $A$ is to the left of $\lscr$ and faces the same way as $\lscr$. Again we count $+1$ if at that instant the car is turning left and $-1$ if it is turning right.

{\small

In algebraic terms,
$$\dg
A(\lscr)=\sum
{\di z=\di\lscr}\;(\po z \leftof \lscr)\cdot \tau
A(z).$$

}

\lemma{3.3}{Let A be a balanced tracing and $\lscr$ a line. If we let $\lscr$ go to infinity while staying parallel to itself and moving to its right, then $\dg
A(\lscr)$ tends to a finite limit that is independent of $\lscr$.}    

This integer is called {\it the degree of the tracing $A$}, and is denoted by $\delta(A)$. It is obviously a signed count of how often the car faces in a particular direction. We can also interpret $\dg(A)$ as the total number of complete $360\deg$ turns the car performs around itself as it goes around the tracing. The concepts are illustrated in figure 3.5.

An interesting theorem relates $\wi$, $\sw$, and $\dg$.

\theorem{3.4}{$\wi(p,A)+\sw(p,A) = \dg(A)$ for any point $p$ and any balanced tracing $A$.}

An illustration of this theorem is given by the example tracing in figure 3.6. Note that at a point $p
1$ below the tracing the sweep number is zero because the car never faces that way. At a point $p
2$ above the tracing the sweep number is zero because the car faces that way twice, once while turning left and once while turning right.

Theorem 3.4 allows us to derive an efficient test for whether a point $x$ is inside a simple polygon $P$. We start with the following lemma:

\lemma{3.5}{If $P$ is a simple polygonal tracing, then $\delta(P)$ is $+1$ or $-1$, depending on whether $P$ is counter- or clockwise oriented.}

Let $m
0, t
0, m
1, t
1, m
2, \ldotss, t
{n-1}, m
{n-1}$ be the moves and turns of the tracing, in their order of occurrence. We define the Boolean predicate $L
i(x)$ as being true if point $x$ is to the left of the line supporting move $m
i$. Then we define the predicate $S
i(x)$ as being $L
i(x)\land L\pr
{i+1}(x)$ if the turn $t
i$ is a left turn, and $L\pr
i(x)\land L
{i+1}(x)$ otherwise (where the index $i+1$ is taken modulo $n$ and ``$\null↑\prime$'' denotes complementation). Intuitively, the predicate $S
i(x)$ is true if $x$ is swept by the turn $t
i$\foot\dag{If $x$ lies on the line of $m
i$, we take $L
i(x)$ as being true or false according to whether we want the resulting test to exclude boundary points of the polygon or not. Either way, it is not necessary to test whether $x$ actually lies between the two endpoints of the move. Also, if the turn $t
i$ is null, we let $S
i(x)$ be false.}.

From theorem 3.4 and lemma 3.5, we conclude that the point $x$ is inside or outside $P$ depending on whether its sweep number $\sw
A(p)$ is $0$ or $\pm 1$. Clearly, we will have one or the other depending on whether the number of terms $S
i(x)$ that are true is even or odd. Therefore, we have 

\theorem{3.6}{The point $x$ is inside the simple polygon $P$ if and only if the following exclusive or yields false  
$$S
0(x)\xor S
1(x)\xor S
2(x)\xor \ldots\xor S
{n-1}(x).$$}

In practice the typical situation will be that $P$ is fixed while $x$ is variable. Thus in the preprocessing stage we can make the distinction between the two forms of $S
i(x)$, as well as precompute the line equation of each side. Then the computation of $L
i(x)$ takes only two multiplications, two additions, and one comparison.

\subsection{3.7. Convex tracings}

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, or all moves are backwards, 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 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.

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.

\input KinFOCS2.tex