\input TR8TwoColFormat \input GeoMacros \input KineMacros

\begfile{KiNarr.tex of November 2, 1983 2:56 pm --- Stolfi}

%  Kinetic Framework - Extended abstract for FOCS '83
%  Reformatted to use TR8TwoColFormat.tex

% Titles and stuff

\pagetitlestuff{
  \title{A Kinetic Framework for Computational Geometry}
  
  \titlerule
  \author{Leo Guibas, Lyle Ramshaw, and Jorge Stolfi}
  \institution{Xerox PARC and Stanford University}
  \titlerule
  \ctrpar\pagewidth pt{\it Extended Abstract}
 }

\support{The work of Jorge Stolfi, who is on leave from the University of S\tilde{\rm a}o Paulo, was partially supported by a grant from Conselho Nacional de Desenvolvimento Cient\acute{\i}fico e Tecnol\acute{\rm o}gico (CNPq).}

\botinsert{\vbox to 1.2 truein{}} % For ACM copyright notice, etc

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

\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. The convolution of two sets}

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^{\transl a}$ the set $B$ translated by the vector $a$, then clearly
$$A\ast B=\union
{a\in A} B^{\transl 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\,\transl 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).

\capfig2cm{Figure 2.1. The convolution of two sets.}

\capfig3cm{Figure 2.2. A property of $A\ast B.$}

\subsection{2.1. Convolution and the outline representation}

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.

\capfig2.5cm{Figure 2.3. The slope-matching rule.}

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.

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

\capfig4cm{Figure 3.1. States and trips.}

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

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.

\capfig3.5cm{Figure 3.2. Moves, turns, and polygonal tracings.}

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}

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

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

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

\capfig3cm{Figure 3.3. Winding number.}

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.

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.

\capfig3cm{Figure 3.4. Sweep number.}

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

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.

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.

\capfig3cm{Figure 3.5. Degreee of a line and a tracing.}

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.

\capfig3cm{Figure 3.6. Relation between $\wi$, $\sw$, and $\dg$.}

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.

\section{4. Operations on tracings}

We now proceed to develop a calculus of operations on tracings, including addition, convolution, and multiplication. In the current write-up we will place emphasis on conveying the intuitive semantics of these operations and conduct most of the discussion in informal terms. We will also rigorously define each operation by algebraic formulas that give the multiplicity of a state in the resulting tracing. However, due to lack of space, discussion of those formulas and a proof of their validity is relegated to a later publication. In general, this proof consists of showing that the resulting multiset of states is a partial tracing, and is integral and balanced whenever the operands are.

\subsection{4.1 Addition and time reversal}

The addition of two (partial) tracings $A$ and $B$ is simply their multiset sum, denoted by $A+B$: the multiplicity of a state in $A+B$ is the algebraic sum of its multiplicities in $A$ and in $B$. The {\it time reversal} of a tracing $A$ consists of the car going through the same sequence of states in the reverse order; clearly, this corresponds to inverting the sign of the multiplicity of every state in $A$, so we denote the resulting tracing by $-A$. 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$. 

\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$. In section 2 we have already seen two examples of affine maps, namely translation by a vector $v$ ($P^{\transl v}$) and $180\deg$ rotation around the origin ($P^N$). An one-to-one affine map $M$ takes a 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 moves, turns, trips, 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^{MM\pr}$. This agrees with our use in section 2 of $A^{N\,\transl x}$ to denote the figure $A$ rotated by $180\deg$ and then translated by the vector $x$.

\subsection{4.3. Convolution}

We are now ready to define the {\it convolution} $A\ast B$ of two tracings $A$ and $B$, which will turn out to be a natural extension of the point set operation defined under that name in section 2. We will define $A\ast B$ by means of a construction procedure that essentially follows the basic rule, the {\it fiber product}, discussed there: 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$.

If $A$ and $B$ have parallel moves, there would be infinitely many pairs of states, one of $A$ and one of $B$, all adding to the same state of the convolution. We avoid this problem by ignoring such pairs, that is, considering only pairs where at least one of the states belongs to a turn. The formulas below embody this convention and give a rigorous definition of convolution:
$$\eqalign{\mu\xpm
{A\ast B}(s)
    =\sum
{{\scriptstyle\scrp {\po x+\po y=\po s}}
           \atop{\scriptstyle {\di x=\di y =\di s}}}
         \mu\xpm
A(x)\tau
B(y)+\mu\xpm
B(x)\tau
A(y)\cr\vsk6
\tau\xpm
{A\ast B}(s)
    =\sum
{{\scriptstyle\scrp {\po x+\po y=\po s}}
           \atop{\scriptstyle\di x=\di y =\di s}}
         \tau\xpm
A(x)\tau\xpm
B(y)\cr}$$

The above imply that convolution is a {\it bilinear operation}: For any tracings $A$, $B$, and $C$, we have $A\ast (B+C)=(A\ast B)+(A\ast C)$, and similarly on the other side. This property is the key both to a better understanding of what convolution means, and to an effective algorithm for computing it. Recall that every tracing can be written as the sum of individual moves or turns. By bilinearity, the convolution $A\ast B$ will be the sum of all the convolutions $A
i\ast B
j$ of a move or turn of $A$ with one of $B$. According to the formulas, we have only to consider the cases of ``turn $\ast$ turn'', ``turn $\ast$ move'', and ``move $\ast$ turn''; the convolution of two moves is always the null tracing. 

The convolution of two left turns $t
1, t
2$ with positions $p
1$ and $p
2$ is a left turn at position $p
1+p
2$. The set of directions swept by each $t
i$ can be viewed as an arc $\alpha
i$ on the unit circle. The states in the convolution $t
1\ast t
2$ then will be exactly those with directions in $\alpha
1\inte\alpha
2$\foot\dag{If one of the turns is greater than $180\deg$, the intersection $\alpha
1\inte\alpha
2$ may consist of two disjoint arcs. In that case the convolution $t
1\ast t
2$ will consist of two left turns.}. See figure 4.1.

\capfig3.5cm{Figure 4.1. The convolution of moves and turns.}

Let us consider now the case of a left turn $t$ convolved with a forward move $m=\la r\sp s\ra$, or vice-versa. We have two subcases: if the orientation of $m$ does not belong to the arc of directions swept by $t$, there are no matching pairs of states, and the convolution $t\ast m$ null. Otherwise, there will be a single state $x$ of $t$ that is parallel to $m$. The convolution $t\ast m$ is the forward move obtained by adding $x$ to every state of $m$, that is, the move $\la r+x\sp s+x\ra$; see figure 4.1. Clearly, these two rules are consistent with the basic rule of adding parallel states of the two operands.

The bilinearity property determines the result of convolutions involving backward moves and/or right turns (that is, elements with negative multiplicities). For example, the convolution of a forward move and a right turn is a backward move, and the convolution of two right turns is a left turn. An example of the convolution of two tracings is shown in figure 4.2. For the statements of the theorems below recall that the term tracing is used to denote an integral and balanced partial tracing.

\capfig3cm{Figure 4.2. The convolution of two polygonal tracings.}

\theorem{4.1}{The convolution of two tracings is a tracing.}

From the discussion above it is clear that the convolution of tracings is both associative and commutative. Furthermore, if $M$ is a {\em linear} map, then $(A\ast B)^M = A^M\ast B^M$. If $v$, $w$ are two vectors, then $A^{\transl v}\ast B^{\transl w} = A^{\transl w}\ast B^{\transl v}=(A\ast B)^{\transl{{v+w}}}$. Therefore, translations of the operands do not affect the shape of the convolution. As a final comment, we note that:

\theorem{4.2}{If $A, B$ are of size $O(n)$, then $A\ast B$ is of size $O(n^2)$.}

This bound is tight, as the example of figure 4.3 shows. This is in contrast with the convex case, to be discussed below. Algorithms for computing general polygonal convolutions are an interesting topic, but will not be discussed further in this paper.

\capfig3.5cm{Figure 4.3. The convolution may have $\Theta(n^2)$ edges.}

\subsection {4.4. Convolution and convexity}

The convolution of convex tracings is fundamentally simpler than the general case. Figure 4.4 illustrates the simple case of convolving a square with a diamond. 

\capfig3cm{Figure 4.4. The convolution of two convex tracings.}

\theorem{4.3}{The convolution of two similarly oriented convex tracings is a similarly oriented convex tracing, obtained by merging the edges of the two factors in slope order.}

As a consequence of this theorem, the convolution of two similarly oriented convex tracings can be computed {\it in linear time}. Note that reversing the sense of traversal on one of the factors reverses the sense of traversal in the convolution, but does not otherwise change the set of result states. Reversing the orientation of one of the factors, however, can have profound effects, as we will see in sections 6 and 7.

\subsection{4.5. Product}

It is easy to check that the winding number function $\wi$ is {\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 process of computing the product is informally as follows. We break every move of $A$ into submoves at every point where it crosses the path of $B$. Analogously, we break every move of $B$ at the points where it crosses $A$. After this is done, all points of a particular (sub)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.5. Note that every move or turn that is copied into the product retains its original orientation.

\capfig3.5cm{Figure 4.5. The product of two tracings.}

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. Fortunately the balance can be restored at those points by adding extra turns. By convention, every such turn is less than $180\deg$, and connects an incoming move derived from one tracing to an outgoing move derived from the other. This turn will bound the regions of highest winding number for the two tracings at that vertex.

For the exact definition of product, we need first introduce the ``displaced winding numbers'' $\wi\xp(s)$ and $\wi\xm(s)$, that give the values of $\wi(p)$ for a point $p$ respectively just ahead and just behind the state $s$. These are given by the formulas
$$\wi\xp(s)=\sum
{r\in (s\sp \infty)}\,\,\,
  \sum
{t\in\laa r\sp \op r\raa} \mu(t)$$
and
$$\wi\xm(s)=\sum
{r\in [s\sp \infty)}\,\,\,
  \sum
{t\in\laa r\sp \op r\raa} \mu(t).$$

The state counting functions for the product are then defined by
$$\eqalign{
\mu\xpm
{A\cdot B}(s)=\mu\xpm
A(s)w\xpm
B(s) + \mu\xpm
B(s)w\xpm
A(s)\cr\vsk6
\tau\xpm
{A\cdot B}(s)=\tau\xpm
A(s)w
B(s)+\tau\xpm
B(s)w
A(s)
    -\tau\xpm
A(s)\tau\xpm
B(s)\cr\vsk3
\null\hskip10pt +\sum
{x\in (\op s\sp s\ra}\,\,\,
    \sum
{y\in \la s \sp \op x)}
      \biglp \Pi
{A,B}(x,y)+\Pi
{B,A}(x,y)\bigrp\cr\vsk6
\null\hskip10pt \pm{1\over2}\sum
{x\in \laa s\sp\op s\raa}
      \biglp \Pi
{A,B}(x,s)+\Pi
{B,A}(x,s)\bigrp\cr\vsk6
\null\hskip10pt -{1\over2}\;\; \Pi
{A,B}(s,s)\cr
}$$
where
$$\Pi
{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 integral balanced tracings $A$ and $B$ is a tracing only if $A$ and $B$ have no oppositely oriented moves or turns with coincident positions.

\theorem{4.4}{The product of two tracings $A$ and $B$ containing no two states, one from $A$ and one from $B$, with the same position and opposite orientations, is a tracing.}

If this condition is violated, the product will be balanced but may contain moves and turns with half-integer multiplicities. In any case, the winding numbers in the product tracing have the following property:

$$\eqalign{\wi
{A\cdot B}(s)=\wi
A(s)\,\wi
B(s)\cr\vsk4
    \null\hskip10pt +{1\over4}\bigglp \sum
{\scrp {\po z=\po s}}\;\mu
A(z)\biggrp
        \bigglp \sum
{\scrp {\po z=\po s}}\;\mu
B(z)\biggrp\cr\vsk4
    \null\hskip10pt -{1\over4}\sum
{\scrp {\po z=\po s}}\;\;
        \biglp \mu\xp
A(z)\,\mu\xm
B(\op z)
          +\mu\xm
A(z)\,\mu\xp
B(\op z)\bigrp.\cr}$$

In particular, if neither $A$ nor $B$ pass through the point $\po s$, this equation reduces to $\wi
{A\cdot B}(s)=\wi
A(s)\wi
B(s)$.

There is another way of looking at the product definition that is quite similar to the basic state-pairing principle used in constructing the convolution. We consider all pairs of states $x, y$ such that $\po y$ is on the ray out of $x$. For every such pair where $x$ occurs in one tracing, and the other tracing {\em moves} through $y$, we add to the product $A\cdot B$ a multiple of the state $x$, depending on the orientation of $y$. Specifically, we use a coefficient of $+1$ if $\di y$ lies to the left of $\di  x$, $0$ if $\di  y = \di x$, and $-1$ if $\di y$ lies to the right. We also consider all pairs $x, y$ where $\po x=\po y$ and $y\in(x\sp \op x)$; for every such pair where one tracing moves through $x$ and the other moves through $y$, we add to the product one copy of the turn $\la x\sp y\ra$. See figure 4.6. As in the convolution, if $x$ occurs $k$ times in one tracing, and the other moves through $y$ $\lscr$ times, we must consider the pair $x, y$ as occurring $k\lscr$ times, and add its contribution that many times to the product tracing. 

\capfig3.5cm{Figure 4.6. The product of two states.}

To see why these rules are equivalent to the ones given above, recall the definition of winding numbers. Clearly, the first rule will add to the product a given state $s$, which occurs $\alpha$ times in $A$ and $\beta$ times in $B$, a total of $\alpha\cdot \wi
B(\po s)+\beta\cdot \wi
A(\po s)$ times. The second rule provides the additional turns needed to balance the product tracing.

From this discussion (and, rigorously, from the algebraic formulas) we can see that product is a bilinear operation, as well as being commutative and associative. Affine maps distribute over product: for any map $M$, $(A\cdot B)^M=A^M\cdot B^M$.

The addition and multiplication of tracings can be seen as a generalization of the union and intersection of figures. Let us define the {\it interior} of a tracing $A$ as the set of points of nonzero winding number with respect to $A$. Now consider the class of tracings whose winding number functions assume no negative values. This class is closed under addition and product; the interior of $A+B$ is the union of the interiors of $A$ and $B$, while the interior of $A\cdot B$ is the intersection of these interiors. As with the convolution, the product of convex tracings is particularly simple.

\theorem{4.5}{If $P$ and $Q$ are similarly oriented convex tracings, then $P\cdot Q$ is a similarly oriented convex tracing corresponding to their classical intersection.}

Even for oppositely oriented convex tracings multiplication has nice properties. The following result, illustrated in figure 4.7, will be useful later on:

\capfig3.5cm{Figure 4.6. The product of oppositely oriented convex tracings.}

\lemma{4.6}{If $P$ and $Q$ are counterclockwise traversed but oppositely oriented intersecting convex tracings and $i$ is the number of their edge intersections, then $\dg(P\cdot Q) = 1-i/2$.}

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

\section{5. The convolution theorem}

In this section we will show how the winding numbers $\wi(x, A\ast B)$ of the convolution are related to the tracings $A$ and $B$, in a manner that is easily interpreted as a generalization of convolution discussion presented in section 2. It is not enough for us to know whether $x$ is ``inside'' $A\ast B$ or not; we would like to know also ``how much inside'' it is, i.e., what is the value of $\wi(x, A\ast B)$. In order to do this, we will have to replace the yes-no test ``$A\inte B^{N\,\transl x}\neq\empty$'' of equation (5) of section 2 by one giving a numeric result. To gain some intuition about what this test should be, let's consider the example of figure 5.1, in which $B$ is a diamond of diagonal $r$, and $A$ is a pair of squares of size $R$, placed less than $r$ away from each other. All tracings are oriented and traversed counterclockwise.

\capfig7cm{Figure 5.1. Interpreting $\wi(p, A\ast B)$.}

The convolution of the two tracings will be a pair of octagons, as shown in the figure; the numbers there show the values of $\wi(p, A\ast B)$ in each ``region'' of the tracing. Now let us see how those numbers could arise from the characterization suggested by equation (5) of section 2. We see that a point $p$ with $\wi(x, A\ast B)=k$ ($k=0, 1$ or $2$) is one for which $A\inte B^{N\,\transl x}$ has exactly $k$ components. This result is on the right track: with only a little more elaboration, it will give us a precise expression for $\wi(x, A\ast B)$. We need only replace ``intersection'' and ``number of components'' by suitable concepts that are applicable to general tracings.

It turns out that we already have the necessary concepts: the multiplication of two tracings is the right replacement for ``intersection'', and the proper way to count the ``components'' of the result is by taking its degree, as defined in section 3.5.

\theorem{5.1.\ {\rm (The convolution theorem)}}{If $A$ and $B$ are two polygonal tracings, then $\wi(x,A\ast B) = \dg(A\cdot B^{N\,\transl x})$ everywhere.}\par

Note that when the convolution $A\ast B$ passes through $x$, the tracings $A$ and $B^{N\,\transl x}$ will generally contain pairs of opposite states, and their product $A\cdot B^{N\,\transl x}$ may be non-integral. This is to be expected, since in such cases the winding number $\wi(x,A\ast B)$ may be fractional, and no integral, balanced tracing can have fractional degree.

We now look at some illustrations of this theorem. Consider the convolution of a square $A$ with a diamond $B$, both oriented and traversed counterclockwise, as in figure 5.2. For a point $x$ inside the convolution ($\wi=1$) the product of the square by the inverted diamond placed at $p$ is a counterclockwise oriented and traversed convex polygon, whose degree is $1$. If $x$ is outside the convolution, the inverted diamond at $x$ does not meet the square, so the product is empty. This gives $\wi=\dg=0$. And if $x$ is on the convolution, then both sides yield $1 \over 2$.

\capfig5cm{Figure 5.2. Interpreting $\wi(p, A\ast B)$.}

Now consider the example of figure 5.3, where the same diamond $B$ is convolved with a square $A$ oriented and traversed in the opposite sense. For a point $x$ in the region of winding number $-1$, the product $A\cdot B^{N\,\transl x}$ is simply $B$ traversed clockwise, which has $\dg=-1$. The case of points, such as $y$, inside the square but outside $A\ast B$ is more interesting. At first glance it may appear that here too the product has degree $-1$. However, a careful examination of all the turns made by the car in the product tracing shows that their sum is indeed $0$. For $z$, in the region with $\wi=1$, the turns of the product add to one complete counterclockwise revolution, so $\dg=1$. 

\capfig5cm{Figure 5.3. Interpreting $\wi(p, A\ast B)$.}

Figure 5.4 shows the two squares of the preceding two examples, which are traversed and oriented in opposite directions, combined into one tracing and convolved with the same diamond. Notice that the region of non-negative winding number is exactly the area of the plane that would be painted black if a diamond-shaped brush were swept along the square. It was precisely for this application that the kinetic framework was originally developed.

\capfig3cm{Figure 5.4. A brush-and-trajectory example.}

\section{6. Some uses of convolution in algorithms}

Besides its intrinsic interest, the convolution operation defined in the previous section can be used as a powerful tool for the development of new geometric algorithms. We will see several instances of this in the present section, as well as an illustration of its use in proving a classical geometric theorem. Some of the new algorithms improve on the currently best known asymptotic time bounds for the problems they solve. Our domain in this section will be convex polygon problems including intersection detection, common tangent computations, and distance computations.

As a warm-up problem, let us study the convolution $C = A\ast A^{N}$, where $A$ is a convex, counterclockwise oriented and directed tracing. An example is shown in figure 6.1. It is easy to see that $C$ is symmetric around the origin $O$ and contains exactly two copies of each edge of $A$, oppositely oriented. From the set-sum interpretation of the convolution we discussed in the previous section, it follows that:

\capfig3cm{Figure 6.1. Diameter via convolution.}

\lemma{6.1}{The diameter of $A$ equals the maximum radius from $O$ to a point of $C$.}

This lemma in effect captures the essence of Shamos' [\Sh] observation that to find the diameter of a convex polygon it suffices to consider all pairs of antipodal points. Thus we have a linear algorithm for computing the diameter of a convex polygon.

We will now see the use of the convolution as a tool for {\it transforming polygon-polygon problems into point-polygon problems}. Let $P$ and $Q$ denote two counterclockwise oriented convex tracings, each with $O(n)$ moves and turns. The following theorem, which is simply a restatement of theorem 5.1 for the convex case, shows how the convolution can be used for intersection detection.

\theorem{6.2}{Convex tracings $P$ and $Q$ intersect if and only if the origin $O$ is inside the convolution $P\ast Q^N$.}

If $P$ and $Q$ are disjoint, then the next theorem shows how the convolution can be used for distance computations.

\theorem{6.3}{For disjoint convex tracings $P$ and $Q$, $\dist(P,Q) = \dist(O,P\ast Q^N)$. This is true in any $L
p$ metric.}

The next two theorems (figures 6.2 and 6.3) give similar reductions for common tangent problems.

\theorem{6.4}{If $t$ is a tangent from the origin $O$ to $P\ast Q^N$ at point $x-y$, with $x$ on $P$ and $y$ on $Q$, then $t+y$ is an inner common tangent of $P$ and $Q$, touching $P$ at $x$ and $Q$ at $y$ respectively.}

\capfig3cm{Figure 6.2. Inner common tangents via convolution.}

Recall that $\op Q$ denotes $Q$ with its orientation reversed. Then we have:

\theorem{6.5}{If $t$ is a tangent from the origin $O$ to $P\ast (\op Q)^N$ at point $x-y$, with $x$ on $P$ and $y$ on $Q$, then $t+y$ is an outer common tangent of $P$ and $Q$, touching $P$ at $x$ and $Q$ at $y$ respectively.}

\capfig3cm{Figure 6.3. Outer common tangents via convolution.}

These theorems give us obvious algorithms for computing the common tangents of two convex polygons, detecting if they intersect, and computing their distance. We merely apply an appropriate point-polygon algorithm to some convolution of the two polygons. If the convolution is generated explicitly, the running time will be linear in the total number of sides. However, it is possible to solve each of those problems in sublinear (and even logarithmic) running time. The basic idea is to emulate the point-polygon algorithm while computing only those parts of the convolution that the algorithm needs to look at.

Suppose, for example, that as part of the emulation of a point-polygon algorithm, we desire to test on what side of the move $m$ of $P\ast Q^N$ the origin lies. Suppose further that we know that $m$ comes from edge $e$ of $P$. As we know, $m$ is then the vector sum $e+v$ for some vertex $v$ of $Q$. If we can determine $v$, then we can place $e$ in the same position in the plane it will occupy in the convolution. To find $v$, we simply have to locate $e$ according to slope in the edge list of $Q$. We can do this by binary search in time $O(\lg n)$. Thus we can place an edge in the convolution and test a point against it in total time only $O(\lg n)$. This example illustrates the idea that constant-time tests in a point-polygon algorithm can be implemented via convolution as $O(\lg n)$ time tests in the polygon-polygon case. Since $O(\lg n)$ algorithms for the point-polygon versions of the above four problems are well-known, it follows that, via the convolution transform, we have $O(\lg^2 n)$ algorithms for the polygon-polygon versions.

By being cleverer, we can actually get $O(\lg n)$ algorithms for all these problems in a uniform way. The idea is, roughly, that we can get valuable information in the situation described above by testing against an edge that is placed by a constant-time computation ``near'' the convolution. The details will be reported elsewhere. Thus we have a different derivation of a result first obtained by Overmars and van Leeuwen [\OvL] for the common tangents and by Chazelle and Dobkin [\CD] for intersection detection. The $O(\lg n)$ algorithm for distance computation is a new result\foot\dag{We have just been informed that H. Edelsbrunner has independently obtained the same bound.}.

Some of the power of the concepts we have been developing can be seen also from the following derivation of a classical geometric fact. Suppose that $P$ and $Q$ intersect and let $i$ denote the number of edge intersections and $t$ the number of (outer) common tangents of $P$ and $Q$. Then we have
$$\vbox{\halign{\rt{$ # $}\lft{$\null #$}\hskip12pt minus10pt\rm #\cr
  1-{i\over 2} = \dg(P\cdot \op Q)(lemma 4.6)\cr
	       = \wi(O, P\ast (\op Q)^N)(theorem 5.1)\cr
	       = \dg(P\ast(\op Q)^N)-\sw(O, P\ast(\op Q)^N)(theorem 3.4)\cr
	       = 1-{t\over 2}(lemma 3.2),\cr}}$$
so we have proved:

\theorem{6.6}{If $P$ and $Q$ are two intersecting convex polygons, then their number of edge intersections equals the number of their common tangents.}

\section{7. Monostrofic tracings and applications}

In this section we consider a class of tracings, the {\it monostrofic tracings}\foot\ddag{The word ``monostrofic'' is formed from two Greek roots that mean ``single-turn''. }, that generalize convex tracings. As we will see, these tracings have many special properties and can be used to advantage in deriving new algorithms in computational geometry. We will use them in this section as a tool for developing algorithms for testing whether convex polygons fit into other convex polygons. More formally, we have the following definition.

\definition{7.1}{A tracing is called {\it monostrofic} if it is a tour in which the car faces in each direction exactly once.}

Obviously all convex tracings are monostrofic.

\lemma{7.1}{The convolution of two monostrofic tracings is monostrofic.}

This lemma provides us with a family of examples of non-convex monostrofic tracings:  the convolutions of two oppositely oriented convex tracings, such as the convolution of the oppositely oriented square and diamond shown in figure 5.3. These tracings arise, for instance, in computing the outer common tangents of two convex polygons via the convolution construction. Recall from the last section that the inner common tangents of two similarly oriented convex tracings $P$ and $Q$ correspond to the tangents from the origin to $P\ast Q^\N$, which is also a convex tracing. The outer common tangents, however, correspond to the tangents from the origin to $P\ast (\op Q)^\N$, which is monostrofic but non-convex. This situation is somewhat puzzling at first. Could it be that outer common tangents are more difficult to compute than inner common tangents?

Intuitively we expect the answer to be no. And this turns out to be so because the algorithms that find the tangents from a point to a convex tracing also work for computing the tangents from a point to a monostrofic tracing! We do not have the space to develop this observation further here, but this fact is indicative of the many properties of convexity that monostrofic tracings share. In a monostrofic tracing the car is always turning left or always turning right. If we assume, without loss of generality, that the car is always turning left then the lemma below summarizes a number of properties of monostrofic tracings that will be important in the application we want to explore below. An example of a monostrofic tracing illustrating the theorem is shown in figure 7.1.

\capfig3.5cm{Figure 7.1. A monostrofic tracing.}

\lemma{7.2}{Left-turning monostrofic tracings

\item are closed under convolution
\item have degree equal to 1
\item have no regions of winding number greater than 1
\item have at most one region of winding number equal to 1.

\tp Such a region is convex, bounded, and either to the left (in the orientation sense) of all sides, or to the right of all sides.}

We now proceed to study the issue of finding placements of one or more convex polygons in another. By placements we mean translations that cause the enclosed polygon to be fully contained in the enclosing polygon. Notice that we do not allow rotations of the given polygonal shapes.

Suppose that a monostrofic tracing of the form $P\ast (\op Q)^\N$ has a region of winding number 1. What does that region represent? For each point $z$ we have $\dg(P\cdot (\op Q)^{\transl z}) = \wi(z,P\ast (\op Q)^\N)$, so wherever the latter expression equals 1, then so does the former. The fact that $\wi(z,P\ast (\op Q)^\N) = 1$ is equivalent to $\wi(O,P\ast (\op Q)^{\transl z\,\N}) = 1$, i.e., that $P$ and $(\op Q)^{\transl z}$ intersect. But recall, from lemma 4.6, that for oppositely oriented convex tracings $P$ and $\op Q$ the degree $\dg(P\cdot (\op Q)^{\transl z})$ is one minus half the number of edge intersections. The latter number in this case must be zero. Therefore we have proved:

\theorem{7.3}{A point $z$ has winding number 1 with respect to $P\ast (\op Q)^\N$ if and only if either $P$ is entirely contained in $Q^{\transl z}$, or $Q^{\transl z}$ is contained entirely in $P$.}

We can make a counterclockwise traversed convex tracing out of the region of winding number 1, to be denoted by $P\vdash Q$. Some useful properties of $P\vdash Q$ are given in the two lemmata below.

\lemma{7.4}{The tracing $P\vdash Q$ can be computed in linear time.}

We can distinguish whether it is $P$ that can fit in $Q$ or vice-versa as follows:

\lemma{7.5}{If $Q$ fits in $P$ then all sides of $P\vdash Q$ are portions of sides of $P$ (in the convolution); if $P$ fits in $Q$ then they are all portions of sides of $Q$; and if neither statement is true, then $P\vdash Q$ is a single full turn.}

Now let us consider the simultaneous and disjoint placement of two convex polygons $P$ and $Q$ into a third $R$, as in figure 7.2. Let $u$ and $v$ respectively denote valid placements of $P$ and $Q$. Then $u$ must be in $P\vdash R$, $v$ in $Q\vdash R$, and by disjointness we must have
$$P^{\transl u}\inte Q^{\transl v} = \empty \hbox{\rm \ or, equivalently\ } v-u\not\in P\ast Q^\N.$$

Thus $v-u \in (Q\vdash R)\ast(P\vdash R)^\N\rslash P\ast Q^\N$, where ``$\rslash$'' denotes set-theoretic difference. The following lemma states that the converse is also true.

\capfig3.5cm{Figure 7.2. Placing two convex polygons into a third one.}

\lemma{7.6}{There exist disjoint placements of two convex polygons $P$ and $Q$ into a third $R$ if and only if
$$(Q\vdash R)\ast(P\vdash R)^\N\rslash P\ast Q^\N  \empty.$$}

This leads to the following rather surprising conclusion:

\theorem{7.7}{It is possible to decide if two convex polygons can be made to disjointly fit into a third, but with no rotations allowed, in linear time.}

Unfortunately this technique does not extend to more than two polygons.

\section{8. Duality}

A natural duality between points and lines in the Cartesian plane has long been known to geometers [\Cox]. Under this duality a point with coordinates $(a, b)$ corresponds to the line with equation $ax+by+1=0$. The point and the corresponding line are called {\it dual} of each other. Geometrically, if $d$ is the distance from the origin $O$ to point $p$, the dual $p\star$ of $p$ is the line perpendicular to $Op$ at distance $1/d$ of $O$ and placed on the other side of $O$ (see figure 8.1). In order to handle all cases, this definition requires that the plane be extended (by the addition of points at infinity) in such a way that it becomes topologically equivalent to a non-orientable surface, the so-called {\it projective plane}. As a consequence of this non-orientability, there is no consistent way to define the ``left side'' of an oriented line, or to define a ``counterclockwise sense of rotation'' for all points of the plane. In particular, this classical dualization prevents us from giving unique and unambiguous duals for all moves and turns.

\capfig3cm{Figure 2.1. A point and its dual line.}

We solve this problem by using a different extension of the plane, that is endowed with the topology of a sphere (and therefore is orientable). Informally speaking, this extension consists in distinguishing a point on the ``top'' side of the plane from its {\it antipode}, a point with same position but on the ``bottom'' side of the plane. For such a point, the meaning of ``counterclockwise'' is defined with respect to an observer standing on the same side of the plane. So, if a car describes a counterclockwise loop on the top side of the plane, a second car on the bottom side that passes through the same positions in the same order will describe a clockwise loop.  We call this extension the {\it two-sided plane} (2SP). One can view this construction algebraically by using homogeneous coordinates, in which a triplet $\hop{x,y\hom w}$ of reals numbers is used to represent the point with Cartesian coordinates $(x/w, y/w)$. In classical homogeneous coordinates we identify the points $\hop{x,y\hom w}$ and $\hop{\lambda x, \lambda y\hom \lambda w}$ for each real $\lambda0$. In the new manifold we only do so if $\lambda>0$. If $\lambda$ is negative, the point $\hop{\lambda x, \lambda y\hom \lambda w}$ is the antipode of the point $\hop{x,y\hom w}$.

A straight line extends to both sides of the 2SP, and therefore it passes through a point if and only if it passes through its antipode. An oriented line has the same direction vector on both sides; however, since the notions of ``left'' and ``right'' are relative to a local observer, a point is to the left of an oriented line $\lscr$ if and only if its antipode is to the right of $\lscr$. The left and right ``half-planes'' of $\lscr$ are well-defined concepts, and their union is the whole 2SP minus the line $\lscr$.

By working on the 2SP, we can define the duality between points and lines so as to preserve relative orientations. Under this mapping, a point $p$ is transformed to an {\it oriented} line $p\star$, and vice versa: the line $p^\ast$ is oriented counterclockwise (as seen from the origin $O$) if and only if $p$ lies on the top side of the plane\foot\dag{The dual of a line passing through the origin is a {\it point at infinity}, and the dual of the origin is the {\it line at infinity}.}. It follows from this construction that a point $p$ lies to the left of an oriented line $\lscr$ if and only if the dual point $\lscr\star$ lies to the left of the line $p\star$.

This duality extends nicely to states, moves, and turns. The dual of a state is a state, the dual of a move is a turn, and the dual of a turn is a move. A move is forward if and only if its dual turn is counterclockwise. The point where the dual turn occurs is the dual of the tangent to the move; it will be on the top side of the plane if and only if the move is oriented counterclockwise as seen from the origin. If we take the dual of every move and turn of a tracing, the result will be another tracing, the {\it dual} of the first.

The concept of duality is another powerful tool for the study of tracings and for the description, analysis, and construction of algorithms dealing with them. By applying it to theorems, proofs, operations, and algorithms we can obtain twice as many results with practically the same effort. For example, an algorithm for computing the convex hull of $n$ points in the plane {\it automatically} becomes an algorithm for computing the intersection of $n$ half-planes. One fact that makes this technique even more valuable is that certain problems are much easier to visualize in one of the two domains than in the other.

Many of the concepts, operations, theorems, and algorithms given above have important dual versions. For example, winding numbers are the duals of degrees: $\wi(p, A)=\dg(p^\ast, A\star)$. The dual of the sweep number is the {\it crossing number} $\kr(\lscr, A)=\sw(\lscr\star, A\star)$, which is a signed count of how many times the tracing $A$ crosses the line $\lscr$. The {\it dual product} of two tracings $A$ and $B$, mentioned in section 4.6, is defined as $A\dpr B=(A\star\cdot B\star)\star$. While computing $A\cdot B$ we insert new turns where two moves pass through the same point; in $A\dpr B$ we add new moves connecting vertices of $A$ and $B$ wherever two turns pass through the same oriented line. Thus we see the duality between the operations of intersection and convex hull.

The geometric dual of a convex polygon which encloses the origin can be defined in the classical projective plane, and has in fact been used by several authors. However, we believe that the 2SP and the concept of tracing as we defined here are the simplest formalism that allows that concept to be extended to arbitrary polygons. It is instructive to consider the example of a convex tracing that does not enclose the origin (figure 8.2). Note that the dual tracing contains points on both sides of the plane, since the original contains both counterclockwise- and clockwise-oriented moves; in particular, the vertex $1\star$ is on top, and $2\star$ is on the bottom. The move $1\star2\star$ follows the shortest possible route, namely the straight line segment connecting those two points, which turns out to be the two rays (one on top and one on the bottom) shown in the figure. If the distinction between top and bottom is ignored, there does not seem to be any simple way of interpreting the dual figure as a convex polygon. As a tracing on the 2SP, however, the dual is a perfectly valid convex polygon. Its interior $R$ consists of the hatched region on the top side of the plane, plus the dotted region on the bottom. For any two points $u,v$ in $R$, the segment $uv$ (with the convention mentioned above) lies entirely in $R$.

\capfig4cm{Figure 8.2. A convex tracing and its dual.}

\section{9. Conclusions}

We have exhibited a new framework for geometric computing based on a set of topological concepts such as direction, tracing, winding number, degree, and sweep number. By the use of fiber products we have a generic way of defining operations on tracings. Our operations generalize classical ones, such as intersection or convex hull, and include powerful new ones, such as convolution. Finally, the precise duality we have introduced helps to elucidate several connections between these concepts.

We believe this new framework offers an important new set of tools for developing, understanding, and verifying geometric algorithms.

\section {10. References}

\ref [\CD] {\refauth{Chazelle, B., and Dobkin, D.}
\reftit{Detection is easier than computation.}
\refpub{Proc. 12th Annual ACM Symp. on Theory of Computing (Apr. 1980), 146--152}}

\ref [\Cox] {\refauth{Coxeter}
\reftit{{\bf Introduction to Geometry}.}
\refpub{John Wiley & Sons, 1969}}

\ref [\EMP] {\refauth{Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D.}
\reftit{Stabbing line segments.}
\refpub{BIT Vol. 22 (1982), 274--281}}

\ref [\Fi] {\refauth{Fischer, M. J.}
\reftit{The mountaineer's problem.}
\refpub{Problem 82-1, J. of Alg., vol. 3 (1982), 177--178}}

\ref [\GP] {\refauth{Guillemin, V., and Pollack, A.}
\reftit{{\bf Differential Topology}.}
\refpub{Prentice Hall, 1974}}

\ref [\GrY] {\refauth{Graham, R. L., and Yao, F. F.}
\reftit{Finding the convex hull of a simple polygon.}
\refpub{J. of Algorithms (to appear)}}

\ref [\IK] {\refauth{Iyanaga, S., and Kawada, Y.}
\reftit{{\bf Encyclopedic Dictionary of Mathematics} {\rm (2nd. ed.)}.}
\refpub{MIT Press, Cambridge, Mass., 1968}}

\ref [\Kn] {\refauth{Knuth, D. E.}
\reftit{{\bf TEX and Metafont}.}
\refpub{Digital Press, 1979}}

\ref [\La] {\refauth{Lang, S.}
\reftit{{\bf Differential Manifolds}.}
\refpub{Addison-Wesley, 1972}}

\ref [\OvL] {\refauth{Overmars, M. H., and Leeuwen, J. van}
\reftit{Maintenance of configurations in the plane.}
\refpub{Journal of Computer and System Sciences [Issue unknown] (1981), 166--204}}

\ref [\Ni] {\refauth{Nievergelt, J.}
\reftit{Sweep-line algorithms in computational geometry.}
\refpub{Personal communication}}

\ref [\PM] {\refauth{Preparata, F. P., and Muller, D. E.}
\reftit{Finding the intersection of $n$ half-spaces in time $O(n\log n)$.}
\refpub{Theor. Comp. Sc. Vol. 8 (1979), 44-55}}

\ref [\Sch] {\refauth{Schwartz, J. T.}
\reftit{Finding the minimum distance between two convex polygons.}
\refpub{Information Processing Letters Vol. 13, 168--170 (1981)}}

\ref [\Sh] {\refauth{Shamos, M. I.}
\reftit{Computational geometry {\rm (Ph. D. thesis)}.}
\refpub{Yale Univ. (Dec. 1977)}}

\ref [\TLP] {\refauth{Lozano-Perez, T.}
\reftit{Spatial planning: A configuration space approach.}
\refpub{IEEE Trans. on Comp. To appear Feb. 1983}}

\ref [\Tou] {\refauth{Toussaint, G. T.}
\reftit{Solving geometric problems with the ``rotating caliper''.}
\refpub{Proceedings of Melecon '83, Athens, Greece}}

\vskip 20pt \hrule

\vfill\eject\end


�ʽ˜J˜:J˜<˜`˜J˜�J˜å
J˜B—˜J˜Î
——˜%˜J˜�
J˜ãJ˜ß
—˜"J˜ÊJ˜ÎJ˜‡J˜¿—˜J˜¡	J˜{——˜(˜J˜·J˜ J˜5J˜1—˜=J˜»J˜3J˜ºJ˜ÅJ˜œJ˜ßJ˜å——˜˜J˜é—˜#J˜íJ˜�J˜ìJ˜*J˜ïJ˜–J˜ø—˜4J˜µJ˜@J˜ºJ˜ê—˜)J˜¬J˜ÓJ˜êJ˜¾
J˜ç—˜+J˜ÂJ˜ÈJ˜ÇJ˜÷J˜é—˜=J˜òJ˜÷J˜-J˜NJ˜ÀJ˜(J˜½J˜ÑJ˜&J˜{J˜ºJ˜]J˜�J˜ŽJ˜bJ˜è
J˜éJ˜9J˜8J˜\J˜ÓJ˜BJ˜�
J˜‘
J˜�J˜§J˜³
J˜Ì—˜"J˜æ
J˜HJ˜�
J˜WJ˜†J˜ê
——˜#˜J˜µ—˜,J˜Ø—˜8J˜Ò—˜J˜åJ˜³J˜çJ˜ÐJ˜¥J˜>J˜ìJ˜ðJ˜CJ˜=J˜±J˜QJ˜ý
J˜H—˜-J˜¢
J˜@J˜²
J˜¨—˜J˜™J˜èJ˜7J˜ôJ˜µJ˜�J˜ä
J˜°
J˜Ó
J˜ïJ˜…
J˜ªJ˜5J˜ƒJ˜ö
J˜×J˜¬
J˜›
J˜NJ˜Á
—˜#J˜ï——˜$˜J˜ÝJ˜8J˜°J˜ý
J˜¡
J˜øJ˜ÂJ˜8J˜ÁJ˜8J˜½J˜8——˜3˜J˜ÀJ˜¢J˜2J˜WJ˜ü
J˜…J˜zJ˜tJ˜~J˜aJ˜Ý
J˜?J˜MJ˜ã
J˜?J˜åJ˜›J˜¬J˜ßJ˜˜
——˜2˜J˜šJ˜J˜/J˜IJ˜ÚJ˜�J˜1J˜.J˜³
J˜…
J˜›J˜ÀJ˜È
J˜Ç
J˜EJ˜SJ˜ú
J˜ƒJ˜±
J˜HJ˜®
J˜:J˜š
J˜H——˜˜J˜¦J˜3J˜ï	J˜‹J˜›J˜šJ˜ìJ˜šJ˜¸
J˜7——˜˜J˜ðJ˜†
——˜˜J˜µ
J˜jJ˜¼
J˜…
J˜yJ˜’
J˜¦
J˜bJ˜eJ˜Ä
J˜€
J˜µ
J˜¬
J˜|J˜–
J˜ 
J˜——J˜J˜—…—2Ú
6�