\input CgNHdr
\begfile{CgN9Garbage.tex of August 4, 1983 1:41 pm --- Stolfi}

% garbage from CgN9.tex

\chapter{8G}{GARBAGE DELETED FROM CgN9}

To simplify the prose, we will refer to the elements of $P$ as the {\it sites}, and $x$ will be called the {\it query}.

If the points  $\rset{\dist(p,x)\relv p\in P}$ and selecting the minimum.

The trivial algorithm for finding the closest point  consist in computing all distances $\rset{\dist(p,x)\relv p\in P}$ and selecting the minimum. This requires $\Theta(n)$ time for points in the plane ($\Theta(kn)$ if the points belong to a $k$-dimensional space). Since in general every coordinate of every point must be examined, this algorithm is optimal.

This diagram consists of is a subdivision of the space $\Sscr$ into disjoint regions, with the property that two query points fall in the same region if and only if they have the same nearest site. E

If the points  $V(\set{p
1, p
2, \ldots, p
m})$ \item 

\section{8.1. The Voronoi diagram in one dimension}

As a warm-up exercise, let's consider first the case where the space $\Sscr$ has dimension 1, i.e. is a straight line. We can think of each point as a real number (its coordinate from some fixed origin on the line), so the Euclidean distance between two points $p$ and $q$ is $\leftv p-q \rightv$.

Let $p$ and $q$ be two sites with $p<q$. A query point $x$ on the line will be closer to $p$ than to $q$ if and only if it is to the left of the midpoint $u=(p+q)/2$; if $x=u$, $x$ will be equidistant from both.\fig2

For each $p\in P$, let $V(p)$ denote the set of all queries $x$ for which $p$ is the only closest data point, i.e. $\dist(x, p)<\dist(x,q)$ for all $q\in P-\{p\}$. Let $p
1 < p
2 < \cdots < p
n$ be the elements of $P$; it is easy to see that $V(p
1)=(u
0, u
1)$, $V(p
n)=(u
n-1, u
n)$, and $V(p
i)=(u
{i-1}, u
i)$ for $1<i<n$, where $u
0=-\infty$, $u
n=+\infty$, and $u
i=(p
i+p
{i+1})/2$.\fig2

If the query is the point $u
i$, for $1\leq i<n$, we have two closest sites at equal distance, namely $p
i$ and $p
{i+1}$. We denote this fact by writing $V(\set{p
i, p
{i+1}})=\set{u
i}$.

The sets $V(p
i)$ and $V(\set{p
i, p
{i+1}})$ can be represented in $O(n)$ space, by a sorted table of the midpoints $u
i$. By using binariy search on $i$, we can locate in $O(\log n)$ time the position if any query $x$ among the points $u
i$. If there is an $i$ such that $u
{i-1} < x < u
i$, then $x\in V(p
i)$ and $p
i$ is the data point closest to $x$. If $x=u
i$ for some $i$, then $x\in V(\set{p
i, p
{i+1}})$, and both $p
i$ and $p
{i+1}$ are the closest sites to $x$. The computation of the midpoints $u
i$ requires the sites to be sorted, so the preprocessing may take $\Omega(n\log n)$ time in the worst case.

These ideas can be easily generalized for an arbitrary space $\Sscr$ with dimension $k$:

\definition{?}{Let $P$ be a collection of points ({\it sites}) from an Euclidean space $\Sscr$. For any subset $K$ of $P$, the {\it Voronoi region $V
P(K)$} corresponding to $K$ is the set of all points $x$ of $\Sscr$ such that the sites of $P$ that are at minimum distance from $x$ are exactly those in $K$. The function $V
P$ is the {\it Voronoi diagram} of the set $P$\foot\dag{\rm Some researchers call it the {\it Dirichlet} or {\it Thiessen} {\it tesselation}; these names are particularly common in Europe.}.}

As above, if $p$ is a single site we write $V
P(p)$ as a shorthand for $V
P(\set{p})$. We will also write $V(K)$ and $V(p)$ whenever the set $P$ is implied by the context. 

The Delaunay diagram can be defined for spaces of arbitrary dimension, and the properties mentioned above can be succesfully generalized. We will now proceed to give mathematical flesh tho these bare assertions.

The figure below shows the Voronoi diagram of a set of ten sites in the plane.\fig6 

This example illustrates several important properties of Voronoi diagrams. Note that the Voronoi region of each site is a convex polygon. If two regions $V(p)$ and $V(q)$ have a non-trivial common frontier, then this frontier is an interval (maybe infinite) of the perpendicular bisector of the segment $pq$, and it is called a {\it Voronoi edge}. The endpoints of those edges are called {\it Voronoi vertices}; three or more edges, and the same number of regions, are incident to every vertex. The collection of regions, edges and vertices of a Voronoi diagram determine a subdivision of the plane, as defined in chapter 5.



of theorem 8.?, let's consider the particular case of a Voronoi diagram in the plane. For every site $p$, ther region $V(p)$ is an open (and possibly unbounded) convex polygon, called a {\it face} of the Voronoi diagram. If nonempty, the region $V(K)$ is called the {\it edge} of $V
P$ corresponding to the pair $\set{p,q}$.

; in the second case, that point is called a {\it vertex} of $V
P$. 
Let us now consider the structure of a three-dimensional Voronoi diagram. This analysis is extended to Voronoi diagrams in arbitrary dimensions by the following result:

The next theorem follows immediately from this definition:


{\bf mention that in a ``general'' set of sites, a subset of $r+1$ sites has affine rank $\max{k,r}$.}
 
\section{8.4. Handling infinite edges}

 So, if a region $V(H)$ meets $\bar{V(K)}$, then it must be entirely contained in $\bar{V(K)}$, and therefore in $\bar{V(K)}-V(K)$. Now, for any convex set $X$ of dimension $r$ the proper boundary $\bar{X}-X$ is either empty or has dimension $r-1$. Therefore, we can conclude that the closure of a Voronoi region of dimension $r$ consists of itself plus other Voronoi regions of

{\bf Stopped here April 12, 1983  11:29 AM >>>}

If and only if $K$ has affine rank $k-r$, and there is a closed $k$-dimensional ball $S\subset \Sscr$ such that $K$ lies on its boundary and $S$ contains no other sites of $P$.}
 
Therefore, the Voronoi diagram in Euclidean space consists of a collection of convex polytopes, each associated with one site. As we saw before, if the dimension $k$ of $\Sscr$ is 1 the Voronoi regions are either closed intervals, half-rays, or the whole real line. If $k=2$, they are convex polygons; if $k=3$, convex polyhedra. The figure below shows a set of ten points in the plane and its Voronoi diagram:\fig5

From the definition, it is clear that every point of $\Sscr$ belongs to at least one Voronoi region. The next theorem shows that the converse is almost true:

\lemma{8.?}{A point $x\in V(p)$ belongs to some other Voronoi region if and only if it is on the boundary of $V(p)$.}

\proof{If $x\in V(p)\inte V(q)$, then $p$ and $q$ are both the closest sites to $x$, implying $dist(x, p)=dist(x, q)$. It follows $x\in B(p, q)$. Since $V(p)$ lies entirely in one side of $B(p, q)$ and has $x$ in common with it, $B(p, q)$ is a supporting plane of $V(p)$, and therefore $x$ is on the boundary of $V(p)$.

\pp As for the converse, let $x$ be on the boundary of $V(p)$, and consider the set $\Rscr(r)$ of Voronoi regions other than $V(p)$ intersected by a ball $B$ centered at $x$, as a function of its radius $r$. As $r$ goes to zero, $\Rscr(r)$ decreases monotonically according to $\subset$. Since $x$ lies on the boundary of $V(p)$, $B$ always contains some point that is not in $V(p)$, and therefore $\Rscr(r)$ is not empty for all $r$. It follows there is some region $V(q)\neq V(p)$ that is intersected by all such balls, implying that $x$ is also on the boundary of $V(q)$. Since Voronoi regions are closed sets, $x$ belongs to both $V(p)$ and $V(q)$.}

From this theorem we conclude immediately that Voronoi regions have pairwise disjoint interiors, and in fact every point of $\Sscr$ is either in the interior of exactly one Voronoi region, or on the boundary of two or more regions.

Let $K$ be any subset of $P$, and let us denote by $V(K)$ the set of all points $x\in Sscr$ that belong to all Voronoi regions of the sites in $X$ of Consider the set $X=\inter
i V(p
i)$ of all points of $\Sscr$ that belong to $m\geq 2$ specific Voronoi regions, say $V(p
1), V(p
2), \ldots, V(p
m)$, and to no other. Obviously $X$ is a convex set, all its points are equidistant from all sites $p
i$, and are closer to the sites $p
i$ than to any other site in $P-\set{p
1, p
2, \ldots, p
m}$. It follows that , it is contained in all bisectors $B(p
i, p
j)$ with $1\leq i<j\leq m$.   Voronoi diagram is a decomposition of $\Sscr$ into convex polytopes that have pairwise disjoint interiors. In fact, even more is true: a point o the . In particular, a Voronoi diagram in the plane divides the latter into $n$ convex polygons.

The boundary of a convex polygon consists of a finite number of straight lines, rays or segments (without their endpoints), which are called the {\it Voronoi edges} of that region (the interiors of the Voronoi regions) separated from each other by a network of line segments, rays and straight lines. In the next section we will characterize the elements of this network.

An edge of a planar Voronoi diagram that lies between two regions $V(p)$ and $V(q)$ is  by theorem 8.? a subset of the bissector $B(p, q)$, and similarly a vertex 

\digress{These results can be generalized to spaces of any dimension $k\geq 1$, by taking $k$-balls instead of circles, and taking $k$ points intead of two in lemmata 8.4 and 8.5.}

The interior of a region is called (for reasons that will be clearer later on) a {\it face} of the Voronoi. If $V(p)$ and $V(q)$ meet at a point $x$, then $x$ is equidistant from $p$ and $q$. So, $V(p)\inte V(q)$ is a (possibly empty) subset of the bisector $B(p,q)$. Since $V(p)$ and $V(q)$ are closed and convex, the same is true of their intersection; i.e. the latter is either the empty set, a single point, a line, a closed ray, or a closed segment. The endpoints of $V(p)\inte V(q)$, if any, are called {\it Voronoi vertices}; the rest of $V(p)\inte V(q)$ is denoted by $e(p,q)$, and if not empty, is called the {\it Voronoi edge between $V(p)$ and $V(q)$}.  There is a simple characterization of Voronoi vertices, edges and faces:

\theorem{8.6}{A point of the plane is a Voronoi vertex iff it belongs to three or more regions.}

\proof{First, the ``only if'' part. Let $v$ be a Voronoi vertex, i.e. an endpoint (or the only point) of $V(p)\inte V(q)$, for some $p$ and $q$. Any point of the bisector $B(p,q)$ is equidistant from $p$ and $q$, and therefore is either in both regions or in neither of them. Any ball $S$ centered at $v$ will meet a point $x$ of $B(p,q)$ that is not in $V(p)\inte V(q)$; the point $x$ will be neither in $V(p)$ nor in $V(q)$, and therefore will be in some other region.\fig3 So, any ball centered at $v$ meets some region other than $V(p)$ and $V(q)$. Since the set of regions met by one of those balls is a monotonically decreasing function of its radius, we can conclude that some region $V(r)$ will be met by all such balls. Therefore, $v$ is on the boundary of $V(r)$; since regions are closed sets, we conclude that $v$ is in three distinct regions, namely $V(p)$, $V(q)$ and $V(r)$.  \pp Conversely, let $v$ be a point that belongs to $m\geq 3$ regions. By lemma 8.3, $v$ is the center $C$ of a $P$-free circle passing through $m$ points. Let $p$ and $q$ be two consecutive points on that circle. There is an half-plane $H$ determined by $pq$ that does not contain any of the remaining $m-2$ points. Let $r$ be the open ray of $B(p,q)$ with origin $v$ and pointing into $H$.\fig3 By lemmata 8.5 and 2.???D, there is a $P$-free circle $C\pr$ passing through $p$ and $q$ whose center $c\pr$ lies in $r$. The point $c$ will belong to (at least) $V(p)$ and $V(q)$; by the convexity of the regions, the whole segment $vc\pr$ will also be in $V(p)\inte V(q)$, i.e. it will be part of a Voronoi edge.

\pp On the other hand,  the remaining $m-2$ points will be interior to any circle $C\prr$ passing through $pq$ and with center $c\prr$ on $B(p, q)-r-\set{v}$. Therefore, $v$ is an endpoint of the Voronoi edge $e(p, q)$.}

\theorem{8.7}{A point of the plane belongs to a Voronoi edge iff it belongs to exactly two regions.} \proof{By definition, apoint of the plane belongs to a Voronoi edge iff it belongs to two regions but is not a Voronoi vertex. By Theorem 8.7, the conclusion is immediate.}

\theorem{8.8}{A point belongs to a Voronoi face iff it belongs to exactly one Voronoi region} \proof{The intersection of two Voronoi regions is contained in the bisector of the corresponding data points, and since the  latter is a supporting line for either region, it follows that a point that is common to two regions is on the boundary of both. Therefore, a point interior to a region does not belong to any other region.  \pp Conversely, let $x$ belong to exactly one region $V(p)$. Suppose $x$ is on the boundary of $V(p)$; then any ball centered at $x$ would contain a point not in $V(p)$. Since every point of the plane belongs to some region, and the set of regions met by such a ball is a monotone function of its radius, there is some region $V(q)\neq V(p)$ that is met by all such balls. But then $x$ would be on the boundary of $V(q)$, and therefore in $V(q)$ itself, a contradiction. It follows that $x$ is interior to $V(p), i.e. belongs to a Voronoi face.}

{\bf ...to here <<<}

\lemma{8.5 {\rm the ``bubble'' lemma)}}{If there is a $P$-free circle $C$ through the points $p$ and $q$, and the arc $paq$ contains no points of $P-\set{p,q}$, then $a$ is in the interior of a $P$-free circle $C\pr$ passing through $p$ and $q$.}

\proof{Let $H$ be the half-plane determined by $pq$ and containing $a$. Let $X$ be the set of all points of $P$ that are interior to $H$. If $X$ is not empty, the preceding lemma gives an $X-free circle $C\pr$ passing through $p$, $q$ and some $x\in X$. If $X$ is empty, take any point $x$ in $H-C$, and let $C\pr$ be the circumcenter of $pqx$.\fig3 In either case, lemma 2.???D implies $C\inte H\subset C\pr\inte H$ and $C\pr-H \subset C-H$. We cnclude $C\pr$ is $P$-free and,  since $x$ is not in $C\inte H$, the latter must be a proper subset of $C\pr\inte H$, {\bf ???} $a$ must be interior to $C\pr$.}

An informal way of stating this lemma is by saying that a $P$-free circle $C$ can be ``squeezed'' between any two consecutive points of $P$ on its periphery, so that it will engulf the arc of $C$ that lies between those two points.

his restriction The post-office problem for spaces of higher dimension is perhaps even more important than the planar version, but unfortunately most techniques that work well for  To make this problem precise, we must specify the nature of the sites and query points, as well as what is meant by ``closest''. In other words, we must specify a metric space $\Sscr$ from which the points will be taken, and an associated metric $\dist$ which defines the distance between evry pair of points. We will assume that sites and queries are points of some Cartesian space $\Sscr=\reals↑k$ of fixed dimension $k$; actually, most of our discussion will be confined to the planar case ($k=2$). The distance between two points $p$ and $q$ will be denoted by $\dist(p, q)$, and most of the time it will be the usual Euclidean metric. 

The only site that is closest to a site $p$ is $p$ itself\foot\dag{Since $P$ is by assumption a {\it set} if points, it contains no repeted elements. This may not be true in many practical situations, but the complications this causes are minor.}, implying $p\in V(p)$ for all $p$. In fact, if the closest pair of sites is $d$ apart, then the open ball of radius $d\over 2$ centered at $p$ is entirely contained in $V(p)$, implying that $p$ is always an interior point of $V(p)$.

Combining this result with lemma 8.3, we see that

\theorem{8.9}{An internal face of $\Dscr(P)$ with $m$ sides is a convex polygon, whose points lie on a circle centered at a Voronoi vertex of degree $m$.}

A result similar to theorem 8.8 (and whose proof we leave to the reader) relates the external face of $\Dscr(P)$ to the Voronoi vertex at infinity $\omega$:

\theorem{8.10}{The infinite regions of $\Vscr(P)$ are $V
{p
1}, V
{p
2}, \ldotss, V
{p
m}$, in {\it clockwise} order, if and only if $p
1, p
2, \ldotss, p
m$ are the vertices of the external face of $\Dscr(P)$, in {it counterclockwis} order.}

Although our algorithms can handle the degeneracies implied by four cocircular points, in this section only we will assume that such degeneracies do not arise, so we can speak unambiguously of the Delaunay triangulation of the $n$ sites. If $S$ denotes our collection of sites, then $D(S)$ will denote the Delaunay triangulation of $S$.\par

\theorem{\Th{8D}}{Let $pq$ be an edge of the Delaunay, and let $r, s$ be two sites such that the quadrilateral $Q$ with vertices $prqs$ (in that order) is convex. Then the internal angles of $Q$ satisfy the relation $\hat p+\hat q > 180\deg > \hat r+\hat s$.}

\proof{Let $C$ be a $P$-free circle passing through $p$ and $q$ and through no other sites. Since $Q$ is convex, the segment $rs$ must cross $pq$ at some point $o$ inside $c$. The sites $r$ and $s$ must be outside $C$; so, there are two points $r\pr$ and $s\pr$ where $C$ intersects $r$ and $s$, respectively.\fig3

\pp Consider now the internal angles of the quadrilateral $Q\pr=pr\pr qs\pr$. Since $Q\pr$ is inscribed in a circle, each pair of opposite angles must add to $180\deg$ (To see why, consider the arcs of $C$ subtended by each angle of $Q\pr$). Now, since $r\pr$ and $s\pr$ are interior to the triangles $prq$ and $qsp$, we can conclude that the angles at $p$ and $q$ in $Q$ are definitely greater than those in $Q\pr$. Also, the angles at $r$ and $s$ in $Q$ are definitely smaller than the angles at $r\pr$ and $s\pr$ in $Q\pr$. We conclude that, in the quadrilateral $Q$, $\hat p+\hat q > 180\deg > \hat r+\hat s$.}

The converse runs as follows: let $p,q$ be two sites. Then $pq$ is an edge of the Delaunay if and only if for every pair $r, s$ of sites, either Every Delaunay edge is a chord of a $P$-free circle, so in particular it cannot pass through any of the sites. In fact, even more is true:

\lemma{\Th{11}}{Two sites $p, q$ are vertices of the same interior (resp. exterior) face of the Delaunay if and only if the corresponding Voronoi regions are incident to the same finite (resp. infinite) Voronoi vertex\foot1{{\bf This lemma is probably superfluous. Theorems \Th{9C} and \Th{10} are enough to prove that the Delaunay and Voronoi are duals of each other (there should be a theorem to this effect in chapter 5). Then lemma \Th{11} folow from properties of dual subdivisions.}}.}

\proof{Let $p
0, p
1, \ldots, p
{m-1}$ be the vertices (sites) on the boundary of a Delaunay face $F$, in counterclockwise order as seen from a point interior to the face. Let us denote by $e
{ij}$ the Voronoi edge (if any) between $\V\set{p
i}$ and $\V\set{p
j}$, {\it oriented counterclockwise as seen from $p
i$}. (Note that $e
{ji}$ is the same edge as $e
{ij}$, taken with opposite orientation.) Since there is a Delaunay edge $p
ip
{i+1}$ between any two consecutive sites\foot\dag{Including $p
{m-1}$ and $p
0$. All indices in this proof are to be taken modulo $m$.}, the Voronoi edge $e
{i,i+1}$ (and $e
{i-1,i}$) exists for all $i$.

\pp By theorem \Th{10}, we know that $e
{i,i-1}$ and $e
{i,i+1}$ occur consecutively (in that order and in the forward direction) on the boundary of $\V\set{p
i}$. It follows that the destination of $e
{10}\pr$ is a Voronoi vertex $v$ (possibly $\omega$) that is also the origin of $e
{12}$. Since $v$ is the destination of $e
{21}$, and $e
{23}$ follows $e
{21}$ around $\V\set{p
2}$, we conclude $v$ is also the origin of $e
{23}$. In the same way, we conclude that all edges $e
{i,i+1}$ have a common origin $v$.

\pp If $F$ is an interior (i.e., bounded) face, then at least one of the angles $p
{i-1}p
ip
{i+1}$ (say, $p
0p
1p
2$) is convex. But then the counterclockwise angle between $e
{10}$ and $e
{12}$ is less than $180\deg$, meaning that $v$ is finite. Conversely, if $F$ is unbounded then at least one of the angles $p
{i-1}p
ip
{i+1}$ is concave, and a similar reasoning shows that $v$ is $\omega$. Since all faces $\V\set{p
{i}}$ are incident to $v$, this concludes the ``only if'' part of the theorem}

\pp Let us now show the converse. Let $\V\set{p
0}, \V\set{p
1}, \ldots, \V\set{p
{m-1}}$ be the Voronoi faces incident to a Voronoi vertex $v$. If $v$ is $\omega$, those Voronoi faces are unbounded; by theorem \Th7, all sites $p
i$ lie on the boundary of the $\hull(P)$, and any two of them can be connected by a path entirely outside the hull. Since all Delaunay edges are entirely contained in $\hull(P)$, this path will not cross any of them. Therfore, all the $p
i$ lie on the same (exterior) face of the Delaunay.

\pp If $v$ is finite, assume the regions $\V\set{p
0}, \V\set{p
1}, \ldots, \V\set{p
{m-1}}$ occur in counterclockwise order around $v$. Since Voronoi faces are convex, the sites $p
0, p
1, \ldots, p
{m-1}$ must also occur in counterclockwise order around $v$. Since $\V\set{p
i}$ is adjacent to $\V\set{p
{i+1}}$, there is a Delaunay edge $p
ip{i+1}$, for all $i$. Those edges define a star-shaped polygon (as seen from $v$). By theorem \Th{10}, no other edge can be incident to a site $p
i$ from inside the polygon; by theorems \Th9 and \Th{9B}, no Delaunay edges or vetices can lie in its interior. Therefore, the polygon $\langle p
0, p
1, \ldots, p
{m-1}\rangle$ is an (interior) face of the Delaunay}

This lemma has a surprising consequence:

\theorem{8.6}{Two distinct edges $pq$ and $rs$ of $\Dscr(P)$ are either disjoint or have a single endpoint in common.}

\proof{Suppose $p$ lies on $rs$ but is distinct from $r$ and $s$. Then $B(r,p)$ and $B(s,p)$ are parallel, and $C(r,p)\inte C(s,p)=\ety$. \fig4 Since $V
r\subset C(r,p)$ and $V
s\subset C(s,p)$, this contradicts the hypothesis that $r$ and $s$ are connected.

\pp Now suppose $pq$ and $rs$ meet at some point $o$ that is none of the four endpoints.\fig4 This implies the quadrilateral $Q=\langle p,r,q,s\rangle$ is convex; by lemma 8.5, we should have both $\hat p+\hat q>\hat r + \hat s$, and vice-versa --- again, a contradiction. Therefore, if $pq$ and $rs$ have a point in common, it must be an endpoint of both segments.}

Therefore, the edges of the Delaunay diagram do not cross! This fact is all the more surprising if we note that $pq$ may not cross $e
{pq}$, but may cross several other edges $e
{p\pr q\pr}$ ``unrelated'' to it.\fig4

\digress {By considering only the incidence relationships between vertices and edges, and ignoring their coordinates, the Voronoi diagram $\Vscr(P)$ can be viewed as an undirected planar graph; indeed, if we take into account also the incidence between faces, vertices and edges, $\Vscr(P)$ is a specific embedding of that graph in the plane, i.e. a {\it planar map}.

\dp Given an embedding $M$ of a planar graph $G$, we define a {\it dual graph} $G*$ of $G$ by taking the faces of $M$ as vertices of $G*$, and drawing an edge between $f$ and $g$ in $G*$ whenever $f$ and $g$ share an edge in $M$. (The dual of a graph is not uniquely defined, for different embeddings may give rise to non-isomorphic duals.) We know from Graph Theory that  $G*$ is also a planar graph, and therefore can be drawn in the plane without crossing edges.

\dp In view of this, theorem 8.6 may not seem so exciting, since $\Dscr(P)$, viewed as a graph, is clearly the dual of $\Vscr(P)$. However, the planarity theorems from Graph Theory assume that the edges of the dual can be drawn with curved lines, and/or that the vertices of the dual can be positioned arbitrarily in the plane. If we  require that the edges be straight lines, and that the dual vertices are inside the corresponding faces of the original map, it may be impossible to avoid crossing edges, as is the case for the map below.\fig4 If nothing else, this shows that not every convex subdivision of the plane is the Voronoi diagram of some set $P$.

\dp Let $M$ be an embedding of a planar graph $G$, let $G*$ be the dual graph constructed from $M$, and  let $M*$ be an embedding of $G*$. We say that $M*$ is the {\it dual map} of $M$ if and only if the neighbors of a given vertex $f$ of $M*$, in counterclockwise order, are the faces of $M$ adjacent to the face $f$, in the same order. In general, not all embeddings of $G*$ have this property, and those which do are topologically equivalent. The next few theorems show that $\Dscr(P)$ is the dual of $\Vscr(P)$ as a map, not just as a graph.}

\subsection{\Ch8.\Sec3.\Sbsec3. Delaunay diagrams as convex hulls}

{\bf Use quadratic mapping. Perhaps the duality between V and D diagrams could come easier through this.}

\lemma{7.2}{Each convex hull edge is a Delaunay edge.}\par

\proof{The half-plane supporting the edge and not containing the convex hull is a degenerate circle witness to the Delaunayhood of the edge.}\par

\theorem{\Th{16}}{To every oriented circle $C$ on the plane there corresponds a unique oriented plane $\pi(C)$ in three space with the following property: A point $p$ is on (resp. to the left of) $C$ if and only if the image $\lambda(p)$ is on (resp. to the left of) $\pi(C)$.}

\lemma{\Th{50}}{Let $T$ be a set of sites, and $S\subset T$. Any edge of $\D
T$ whose endpoints are both in $S$ is also an edge of $\D
S$.\fig3}

\proof{For any such edge $e$, consider the $T$-free circle that proves $e$ is an edge of $\D
T$. That circle is also $S$-free, and therefore proves $e$ is an edge of $\D
S$.}

\lemma{\Th{51}}{Let $T$ be a set of sites, and $S\subset T$. If $e$ is an edge of $\D
S$ that is not in $\D
T$, then both endpoints of $e$ are connected to $T-S$ in $\D
T$.\fig3}

\proof{Let $u$ be any endpoint of $e$, and $C$ be the $S$-free circle that proves $e$ is an edge of $\D
S$. Since $e$ is not in $\D
T$, $C$ contains some site of $T$ (and only sites of $T$) in its interior. Let $C\pr$ be the largest $T$-free circle that is interior to $C$ and tangent to it at the point $u$. The sites on the boundary of $C\pr$ are all in $T$ except $u$ itself. If there is only one such vertex $t$, lie all on the same face of face of $\D
T$, and are all in $T$ except $u$; therefore,  $S$-free, and therefore proves $e$ is an edge of $\D
S$.}

\proof{For any such edge $e$, consider the ($S\uni T$)-free circle that proves $e$ is an edge of $\D
{s\uni T}$. That circle is also $S$-free, and therefore proves $e$ is an edge of $\D
S$.}

These observations apply equally well to Delaunay triangulations. In particular, the consequences of adding a single new site $q$ to a Delaunay triangulation $\D$ have a simple structure: we have to delete some of the old edges, and add new edges between $q$ and some old sites $p
1, p
2, \ldots, p
m$.    

$\V\pr\set{p}$ will be equal to $\V\set{p}$ minus $\V\pr\set{q}$ and its boundary. So, the only faces that will be affected are the ones whose sites are  $q$ that will be neighbors of $p$ in the dual $\Dscr\pr$ of $\Vscr\pr$..\fig4 Therefore, the addition of $p$ requires that we compute the new region $V
p\pr$, and erase that portion of $\Vscr$ that lies inside it.

The hardest part of this computation is figuring out which points of $P$ will be adjacent to $p$ in $\Dscr\pr$. It is not hard to get one of them: if we locate the region $V
q$ of the original diagram that contains the new point $p$, then $q$ will be the nearest neighbor of $p$ in $P\pr$, and, by lemma 8.11, $p$ and $q$ will be adjacent in $\Dscr(P\pr)$. More than that, the midpoint $o$ of $pq$ will be a point of the edge separating $V
p\pr$ from $V
q\pr$.

It is easy to see that, in the original diagram, $o$ belongs to $V
q$. If we proceed along the bissector $B(p,q)$, starting from $o$ and moving counterclockwise as seen from $p$, we will eventually meet the boundary of $V
q$ at some point $v$. Let $V
r$ be the region of $\Vscr$ that is on the other side of the boundary at that point, i.e. let $e
{qr}$ be the edge of $V
q$ containing $v$.\fig4 The point $v$ is equidistant from $p$, $q$ and $r$, and no other data point is closer to it than those three; therefore, $v$ is a Voronoi vertex of the new diagram. The edge $e
{qr}$ is divided in two pieces by $v$: the one closest to $p$ has to be discarded, but the other will be an edge of $\Vscr\pr$.

The third edge of $\Vscr\pr$ incident at $v$ is on the bissector $B(p,r)$; if we start at $v$ and proceed counterclockwise (as seen from $p$) along that bissector, we will eventually leave $V
r$ at some point $v\pr$, wich will be the next vertex of $V
p\pr$. If we repeat this process, we will obtain all edges and vertices of $V
p\pr$, and eventually we will get back to the point $o$.

At some iteration of this algorithm, it may happen that the edge we are following leaves the current region $V
q$ through some vertex $v$ of the current Voronoi diagram, rather than across an edge.\fig4 In that case, there will be two or more regions of $\Vscr$ abutting at $v$, besides the one from which we came. To continue the traversal, we must move into the region $V
r$ that is immediately adjacent to $V
q↑P$, in {\it clockwise} order as seen from $v$.

One way to avoid this situation is to ensure that no four data points lie on the same circle. Another way is to allow edges of zero length (see the discussion of the `` patched'' Voronoi diagram, in section 8.???): if we hit the boundary of $V
q$ at a vertex $v$, we take either of the edges incident at $v$, and proceed as if we had hit only that edge.

{\bf This is not as simple as it looks. How do we make sure the resulting graph (abstracting from edge lengths) is still planar and properly embedded? I.e., how do we keep the clockwise orderings of edges around adjacent vertices consistent if the edges have length zero? If you throw in numerical errors, the problem becomes frightening; a satisfactory (but not easy) compromise would be an algorihm that works in all cases if exact rational arithmetic is used throughout. Maybe such a disclaimer should be added to the introduction.}

The algorithm below describes these ideas in more detail. We are assuming the Voronoi diagram $\Vscr$ is represented by the data structure discussed in section 8.???.

\algorithm{8.1}{Incremental computation of the Delaunay diagram.}{ \step 1. [Locate nearest neighbor.] {Find the point $q\in P$ that is closest to $p$.} \step 2. [Initialize.] {Let $a$ be the null edge record $\Lambda$. Search the list of edges incident to $q$ in counterclockwise order, and let $b$ point to the one that would follow immediately the edge $(q,p)$ (if $q$ has degree 0, i.e. it is the only point in $P$, set $b\gets \lambda$).} \step 3. [Insert new edge.] {Create a new record $e$ for the directed edge $(p,q)$, and insert it before $a$, and its symmetrical $(q,p)$ after $b$. Otherwise, let $e$ be the first edge incident to $q$, in clockwise order, that .}}

The relationship between the four lifted points that is described in lemma \Th{40A} is a fundamental predicate of three-dimensional geometry:

\definition{\Def6}{We say that four points $p, q, r, s$ of space, in that order, are {\it positively} (resp. {\it negatively}) {\it oriented} if they are not coplanar and the triangle $pqr$ is oriented counterclockwise (resp. clockwise) as seen from $s$.}

The property of being positively oriented is the three-dimensional analog of the $\CCW$ predicate, since $\CCW(a, b, c)$ is true if and only if the directed segment from $a$ to $b$ points to the left as seen from $c$. The analogy is even more evident from the following result:

\lemma{\Th{41A}}{The points $p$, $q$, $r$, and $s$ of $\reals↑3$, in that order, are positively oriented, coplanar, or negatively oriented, depending on whether the determinant
$$\Delta(p,q,r,s)=\det{\matrix4{
    x
py
pz
p1\cr\va
    x
qy
qz
q1\cr\va
    x
ry
rz
r1\cr\va
    x
sy
sz
s1\cr}}\eqno(\Eq6)$$
is positive, zero, or negative, respectively.}

\proof{Let us displace all four points by a parallel translation so that the point $s$ is moved to the origin; that is, consider the points $p\pr=p-s$, $q\pr=q-s$, $r\pr=r-s$, and $s\pr=s-s=(0,0,0)$. Obviously, the four points $p\pr$, $q\pr$, $r\pr$, and $s\pr$ are oriented with respect ot each other in exactly the same way as $p$, $q$, $r$, and $s$. Furthermore, the determinant
$$\Delta(p\pr,q\pr,r\pr,s\pr)=\det{\matrix4{
    x
{p\pr}y
{p\pr}z
{p\pr}1\cr\va
    x
{q\pr}y
{q\pr}z
{q\pr}1\cr\va
    x
{r\pr}y
{r\pr}z
{r\pr}1\cr\va
    0001\cr}}
  =\det{\matrix4{
    x
p-x
sy
p-y
sz
p-z
s1\cr\va
    x
q-x
sy
q-y
sz
q-z
s1\cr\va
    x
r-x
sy
r-y
sz
r-z
s1\cr\va
    x
s-x
sx
s-x
sx
s-x
s1\cr}}$$
is obtained from $\Delta(p,q,r,s)$ by subtracting from the each of the first three columns an appropriate multiple of the fourth. Therefore, the two determinants are equal. By expanding on the four row, we get
$$\Delta(p\pr,q\pr,r\pr,s\pr)=\det{\matrix3{
    x
{p\pr}y
{p\pr}z
{p\pr}\cr\va
    x
{q\pr}y
{q\pr}z
{q\pr}\cr\va
    x
{r\pr}y
{r\pr}z
{r\pr}\cr}}$$

\pp {\bf now prove that this determinant is positive if and only if the triangle $p\pr q\pr r\pr$ is counterclockwise oriented as seen from the origin. We know that it is positive if and only if the vectors $p\pr$, $q\pr$, and $r\pr$ form a right-handed coordinate system. Is that enough? perhaps we should use this in the definition of positively oriented and in lemma \Th{40A}.} }

The algorithms we are going to see in this section are all based on the $\incircle$ predicate, defined below, that given four points on the plane tests whether one of them is inside the circle determined by the other three. Actually, the definition we are going to give is somewhat more involved, and at first may seem a bit counterintuitive. Its justification is that the resulting predicate is mathematically ``cleaner'' (that is, easier to manipulate in proofs) and corresponds to a very simple algebraic predicate in terms of the coordinates of the four points.

In many applications it is convenient to treat straight lines (with the addition of the point at infinity) as circles with infinite radius. Topologically, the two concepts are equivalent: like a circle, a straight line divides the extended plane in two simply connected regions. However, there is no natural criterion for calling one of these regions the ``interior'' of the line, and the other the ``exterior''. We will resolve this ambiguity by specifying an orientation for the line, and substitute the notions of ``left side'' and ``right side'' for ``interior'' and ``exterior''. Mathematical cleanliness then requires we trat circles in the same manner. This justifies the following definitions:

\lemma{\Th{16}}{Every oriented circle is mapped to a planar section of the paraboloid $\Lambda$, and vice-versa.\fig5}

\proof{A straight line $\lscr$ on the $(x, y)$ plane is obviously mapped to the intersection of of $\Lambda$ with a vertical plane passsing through $\lscr$.

\pp Now consider a circle $C$ with center $c$ and radius $r$. A point $p=(x,y)$ is on $C$ if and only if
$$(x-x
c)↑2+(y-y
c)↑2=r↑2,\eqno(\Eq6)$$
which is equivalent to
$$x
2+y
2=(-2x
c)x+(-2y
c)y+(r
2-x
c↑2-y
c↑2).\eqno(\Eq7)$$
But this is precisely the condition for the point $\lambda(p)=(x, y, x
2+y
2)$ to lie on the plane whose equation is 
$$z=(-2x
c)x+(-2y
c)y+(r
2-x
c↑2-y
c↑2),$$
from which the theorem follows.}

\lemma{\Th{16}}{To every oriented circle $C$ there corresponds a unique oriented plane $\pi(C)$ intersecting lambda, and vice-versa, with the property that a point is to the left of $C$, on $C$, or to the right of $C$ depending on whether $\lambda(p)$ is to the left of $\pi(C)$, to the right of $\pi(C)$,  Every oriented circle is mapped to a planar section of the paraboloid $\Lambda$, and vice-versa.}

In fact, even more is true. Let $pi(C)$ be the plane containing the image of a circle $C$ on $\Lambda$. Then, if we replace $=$ by $\leq$ in equation \Eq6, we 
immediately conclude that

\lemma{\Th{17}}{A point $p$ is inside (resp.outside) a circle $C$ if and only if $\lambda(p)$ is below (resp. above) the plane $\pi(C)$}

\subsection{\Ch8.\Sbsec{\Sec2.1}. The $\incircle$ test}

{\bf Fix this. Define the incircle test only for ccw quadrilaterals at first. Leave the extension to collinear points for later?}

\xx{Pieces removed from here}

Another interpretation of the $\incircle$ test can be obtained via the quadratic mapping $\lambda$ defined in the previous section: 

\lemma{\Th{40A}}{The predicate $\incircle(a, b, c, d)$ is true if and only if the triangle $\lambda(a)\lambda(b)\lambda(c)$ is clockwise oriented as seen from $\lambda(d)$.}

\proof{First, consider the case where $a$, $b$ and $c$ lie on a circle $C$ of finite radius. According to lemma \Th{17}, the point $d$ is inside $C$ if and only if its image $\lambda(d)$ on the paraboloid $\Lambda$ is below the plane $\pi(C)$ containing $\lambda(C)$, which is the plane passing through the points $\lambda(a)$, $\lambda(b)$, and $\lambda(c)$. If the points $a$, $b$, and $c$ occur on $C$ in counterclockwise order, then the triangle $\lambda(a)\lambda(b)\lambda(c)$ on the plane $\pi(C)$ will be clockwise oriented as seen from $\lambda(d)$ if and only if $\lambda(d)$ is below $\pi(C)$, i.e., $d$ is inside $C$. If $a$, $b$, and $c$ occur in clockwise order, the situation is reversed: $\lambda(a)\lambda(b)\lambda(c)$ will be clockwise oriented as seen from $\lambda(d)$ if and only if $\lambda(d)$ is above $\pi(C)$, i.e. if and only if $d$ is outside $C$. The theorem then follows from this and from the definition of $\incircle$.\fig6

\pp Now consider the case when the points $a$, $b$ and $c$ are distinct but lie on a common line $\lscr$. The points $\lambda(a)$, $\lambda(b)$, and $\lambda(c)$ determine a unique vertical plane $\pi(\lscr)$ (that also passes through $\lscr$). Let us orient $\lscr$ so that it passes through $a$, $b$, and $c$ in that order (or any cyclic permutation thereof), i.e., so that$\lscr=\circle(a, b, c)$. Let us also define the left half-space of $\pi(\lscr)$ as the one containing the left half-plane of $\lscr$.\fig6

\pp It is obvious from the concavity of $\Lambda$ that $\lambda(a)$, $\lambda(b)$, and $\lambda(c)$ will not be collinear. By analyzing the three possible orderings of $a$, $b$ and $c$ on $\lscr$, we can see that the triangle $\lambda(a)\lambda(b)\lambda(c)$ will be clockwise oriented as seen from $\lambda(d)$ if and only if $\lambda(d)$ lies on the left side of $\pi(\lscr)$, that is, if and only if $d$ lies on the left side of $\lscr$. This concludes the proof.}

Lemma \Th{40A} says that $\incircle(a, b, c, d)$ is true if and only if the points $\lambda(a)$, $\lambda(b)$, $\lambda(c)$, and $\lambda(d)$ are negatively oriented. Therefore, we conclude that

\theorem{\Th{43}}{The predicate $\incircle(a, b, c, d)$ is true if and only if
$$\det{\matrix4{
    x
ay
ax
a↑2+y
a↑21\cr\va
    x
by
bx
b↑2+y
b↑21\cr\va
    x
cy
cx
c↑2+y
c↑21\cr\va
    x
dy
dx
d↑2+y
d↑21\cr}}<0.\eqno(\Eq7)$$}
    
\algorithm{\Alg{0A}}{Triangulation of $n$ points by $x$-sort.}{
\begblock
  \comm{The input is set $P$ of $n\geq2$ points.
    On output, $T$ will be a triangulation of those points.}  
  \step{\sno{\Step0} Sort th epoints by increasing $x$-coordinate,
    breaking ties by $y$-coorcinate. Let the points be
    $p
1, p
2, \ldots, p
n$, in that order.}
  \step{\sno{\Step1} Let $T$ be the graph consisting of $p
1$ and $p
2$
    connected by a single edge. Let $e$ be
    that edge, directed  from $p
2$ to $p
1$.}
  \step{\sno{\Step2} For $i=3,4,\ldots, n$ do:}
    \begblock
      \comm{At this point $T$ is a triangulation of $p
1, p2, \ldots,
        p
{i-1}$. The origin of $e$ is $p
{i-1}$, and its
        right face is the exterior face of $T$.}  
      \step{\sno{\Step3} Set $e\pr\gets e\oprev$.
        Connect $p
i$ to $p
{i-1}$ by a a new edge $f$.}
      \step{\sno{\Step4} \sna{[Walk clockwise around $T$]}
        While $\CCW(p
i, e\pr\org, e\pr\dest)$ do}
        \begblock
          \step{\sno{\Step5} Set $e\pr\gets e\pr\lnext$.
            Connect $p
i$ to $e\pr\org$ by a new edge, and
            repeat step \Step4.}
        \endblock
      \step{\sno{\Step7} \sna{[Walk counterclockwise around $T$]}
        While $\CCW(e\org, p
i, e\dest)$ do}
        \begblock
          \step{\sno{\Step8} Set $e\gets e\lnext$.
            Connect $p
i$ to $e\org$ by a new edge $f$, and
            repeat step \Step6.}
        \endblock
      \step{\sno{\Step9} Set $e\gets f$ and repeat from step \Step2.}
    \endblock
\endblock
}

We can view the whole process as iterated applications of an {\it incremental algorithm} that, given $P$ and a new site $s$, constructs a for the set $P\pr=P\uni\set{s}$.

Suppose we have just added the new site $s$ to $\DT$ by algorithm \Alg{0.5}, resulting in a new triangulation $T\pr$ of $P\pr$. We now apply algorithm \Alg0 to $T\pr$. For simplicity, let us assume $s$ was located in an interior face $F=uvw$ of $\DT$:\fig4

\subsection{\Sbsec{\Sec2.1}. Incremental triangulation}

To apply algorithm \Alg0, we need first construct an arbitrary triangulation of the set $P$, which is not an entirely trivial task. One method we can use is to start from a minimal triangulation (say, two sites connected by an edge), and add to it the remaining sites, one at a time. To insert a new site $s$ into the current triangulation $T$, we first locate the face $F$ of $T$ that contains $s$. If it is an interior face, we connect its three vertices to $s$ by new edges. If it is the exterior face, we connect to $s$ all vertices of $F$ that are visible from $s$.\fig5

\subsection{\Sbsec{\Sec2.2}. Incremental Delaunay triangulation}

In summary, the proposed method for constructing a Delaunay triangulation of $P$ is to begin with a trivial triangulation (two sites and a single edge), use algorithm \Alg{0.5} repeatedly to insert the remaining sites one by one, and then feed the resulting triangulation to the edge-swapping algorithm \Alg0.

A slight variant of this process gives us an {\it incremental} algorithm for Delaunay triangulation. The idea is to apply the edge-swapping algorithm \Alg0 to each intermediate triangulation, after inserting each new site, so that at every stage we have a Delaunay triangulation for the sites added so far. In other words, given a Delaunay triangulation $\DT$ for $P$ and a new site $s$, we construct a Delaunay triangulation $\DT\pr$ for the set $P\pr=P\uni\set{s}$.

Let us consider this variant in more detail. Suppose we have just added the new site $s$ to $\DT$ by algorithm \Alg{0.5}, resulting in a new triangulation $T\pr$ of $P\pr$. We now apply algorithm \Alg0 to $T\pr$. For simplicity, let us assume $s$ was located in an interior face $F=uvw$ of $\DT$:\fig4

All edges in the Delaunay triangulation $\DT$ were known to satisfy the angle condition. What can we say about $T\pr$? are all its edges suspect? Clearly not: the only edges for which the condition may have become false are those adjacent to $F$, namely $uv$, $vw$, and $wu$.

Furthermore, the new edges $su$, $sv$ and $sw$ always satisfy the angle condition, as is easily shown. Since $\DT$ is a Delaunay triangulation of $P$, the circumcircle $C$ of $F$ is $P$-free. The new site $s$ is strictly inside $C$, and therefore the circle $C
u$ passing through $s$ and tangent internally to $C$ at $u$ is $P\pr$-free. In fact, $C
u$ passes through $s$ and $u$, but through no other site of $P\pr$. This proves $su$ is an edge of the Delaunay diagram of $P\pr$, and therefore (by lemma \Th{21}) it satisfies the angle condition in {\it any} triangulation of $P\pr$. The same is clearly true of $sv$ and $sw$.

So, in step \Step1 of algorithm \Alg0 we can initialize $S$ to $\set{uv, vw, wu}$ only, and proceed to the main loop (steps \Step2--\Step4). At this point, the following statements about the current triangulation are obviously true:

\indent 1. Every edge $e=pq$ in $S$ has $pqs$ as its left face.

\indent 2. Every edge that was not in $\DT$ is incident to $s$, and is an edge of the Delaunay diagram of $P\pr$.

Now consider what happens on the execution of steps \Step3--\Step4. If the edge $e=pq$ lies on the exterior face, or satisfies the angle condition, it is simply ignored, and we return to step 2. Otherwise $e$ is deleted from the triangulation $T\pr$, and replaced by the new edge $sr$.\fig3

At this point algorithm \Alg0 would add to the bag $S$ the four edges $pr$, $rq$, $qs$ and $sp$, on the grounds that the swapping of $e$ may have falsified their angle properties. However, by statement 2 above and lemma \Th{21} we know that $qs$ and $sp$ still are ``good'', so we only have to stack $pr$ and $rq$.

Now observe that statement 1 above is still true, since the stacked edges  $pr$ and $rq$ have left faces $prs$ and $rqs$. We will show now that statement 2 too is still true. The only non-obvious part isto show that the new edge $rs$ is a Delaunay edge for $P\pr$.

The right face $prq$ of the deleted edge $e$ was an internal face of the triangulation. The vertices $p$, $q$, and $r$ are all distinct from $s$. By statement 2 the edges $pr$, $rq$ and $qp$ were all original edges of $\DT$, and therefore $prq$ was one of its interior faces. So, its circumcircle $C$ was $P$-free. On the other hand, $C$ contains $s$, for $e$ failed the angle test. Then consider the circle $C
r$ passing through $s$ and tangent internally to $C$ at $r$: this circle $P\pr$-free, and indeed passes through no other site of $P\pr$ other than $r$ and $s$. This proves $rs$ is an edge of the Delaunay diagram of $P\pr$.\fig3

Therefore, when we return to step 2 statements 1 and 2 above are still true. An inductive argument shows that the above reasoning applies to all iterations of steps \Step2--\Step4. Moreover, the proof can easily be applied also to the cases where $s$ is found to lie on the outer face, or on an edge of the triangulation $\DT$. In any of those cases, the insertion of $s$ creates a star-shaped or ``fan-shaped'' region consisting of zero or more new internal faces $sp
0p
1, sp
1p
2, \ldors, sp
{m-1}p
m$ (where $p
m$ may or may not be $p
0$). Every internal face of $T\pr$ that is not one of these is an original face of $\DT$. The same arguments used above show that $sp
i$ is an edge of the Delaunay diagram of $P\pr$.  Therefore, the only edges of $\DT$ that may have had their angle property falsified are $p
0p
1, p
1p
2, \ldots, p
{m-1}p
m$.

These simplifications are implemented in algorithm \Alg1 below:

\algorithm{\Alg1}{Incremental construction of a Delaunay triangulation.}{
\begblock
  \comm{The input is a Delaunay triangulation $\DT$ of $P$,
    and a new site $s$ not in $P$.
    On output, $\DT$ will have been transformed into a Delaunay
    triangulation $\DT\pr$ of $P\pr=P\uni\set{s}$.
    The set $S$ keeeps track of the ``dubious'' edges,
    as in algorithm \Alg0.}
  \step{\sno{\Step0} Locate and insert $s$ in the triangulation $\DT$,
    obtaining a new triangulation $T\pr$.}
  \step{\sno{\Step1} Let $sp
0p
1, sp
1p
2, \ldots, sp
{m-1}p
m$
    be the interior faces of $T\pr$ incident to $s$, in
    counterclockwise order.
    Set $S\gets\set{p
0p
1, p
1p
2, \ldots, p
{m-1}p
m}$.}
  \step{\sno{\Step2} Whle $S\neq\empty$, do}
    \begblock
      \step{\sno{\Step3} Remove some edge $e=pq$ from $S$.
        If $e$ is an interior edge,
        and does not satisfy the angle property, then}
      \begblock
        \step{\sno{\Step4} Let $prqs$
          be the edge quadrilateral of $e$. Swap $e$, and set
          $S\gets S\uni \set{pr, rq}$}
      \endblock
    \endblock
  \step{\nono Repeat from step 2.}
\endblock
}

This is not all, however. In coding this algorithm, the most natural representation for the set $S$ is a stack. If in steps \Step1 and \Step4 the edges are pushed into $S$ in the given order, then the contents of $S$ at any time, from the bottom up, is a path $x
0,x
1, x
2, \ldots, x
k$ starting from the site $x
0=p
0$. Furthermore, by condition 1 the left face of each edge $x
i x
{i+1}$ is the triangle $x
i x
{i+1} s$. These triangles constitute a fan-shaped region with ``center'' at the site $s$. The effect of steps \Step3 and \Step4 on this region is particularly simple: at each iteration, the last triangle is either removed from the region (i.e., the top edge $e$ of $S$ is ignored), or it is replaced by two triangles ($e$ is swapped and two edges are pushed into $S$).\fig4 

Finally, note that every edge $x
i x
{i+1}$ on the stack, except the first one, is folowed in counterclockwise order around $x
i$ by the edges $x
i s$ and $x
i x
{i-1}$. The stack $S$ is then superfluous: given its top edge $e$, we can get the one just below it by computing $e\onext\onext\sym$.

\footprob{\Prob{\Sbsec{\Sec2.0}.1}}{Code algorithm \Alg1 without using the stack $S$.}

The total number of iterations of steps \Step2--\Step4 is easily determined. If in step \Step0 we introduce $m$ new edges connecting the site $s$ to the rest of $T\pr$, then the initial size of $S$ is between $m-2$ and $m$. Every time $s$ gains a new incident edge in step \Step4, two other edges are pushed onto $S$. Every iteration of steps \Step2--\Step4 deletes exactly one edge from $S$. Therefore, if the final degree of $s$ in $\DT\pr$ is $d$, then the total number of iterations is between $2d-m-2$ and $2d-m$.

If $P$ contains $n$ sites, the number of edges in the triangulation $\DT\pr$ is $O(n)$, and so are the degree of $s$ and the running time of algorithm \Alg1 (except possibly for step \Step0, which is discussed below). In fact, all of the $d$ edges incident to $s$ in $\DT\pr$ are Delaunay edges, and so any algorithm that updates $\DT$ to a Delaunay triangulation of $P\pr$ must add at least those edges. We conclude that algorithm \Alg1 is optimal. 

\xx{Analysis}

\xx{Say that it can be done by dropping in one point at a time. Combine this with algorithm \Alg0 to give an $O(n)$ per point, $O(n↑2)$ total time algorithm for the Delunay. Mention simplification where point are sorted before by $x$.}

{\bf STOPPED HERE July 20, 1983 8:10 pm}

\subsection{BEGIN JUNK}

The Dealunay and Voronoi diagrams can be constructed in a rather straightforward way by the following incremental algorithm: starting with an empty diagram, we add the sites one by one, updating the diagram after each insertion. At each step, we have a Voronoi diagram $\V=\V
P$ and a new data point $q\not\in P$; the goal is to construct from them the updated diagram $\V\pr=\V
{P\pr}$ corresponding to the augmented set $P\pr=P\un \set{q}$.

The new Voronoi diagram $\V\pr$ will obviously have one face more than the original diagram $\V$, namely $\V\pr\set{q}$. Let $\V\pr\set{p
1}, \V\pr\set{p
2}, \ldots, \V\pr\set{p
m}$ be the faces adjacent to it in $\V\pr$, in counterclockwise order. The face $\V\pr\set{q}$ will consist of pieces cut out from the faces $\V\set{p
1}, \V\set{p
2},\ldots, \V\set{p
m}$, plus pieces of the Voronoi edges and vertices incident to them. The only new edges in $\V\pr$ will be those on the boundary of $\V\pr\set{q}$; that is, the addition of a new site cannot create new edges between old faces. An edge of $\V$ will disappear completely only if it separates two of the $\V\set{p
i}$.\figno(\Fig{10})5

Let us recast these statements in terms of Delaunay diagrams:

\lemma{\Th{49}}{Any edge of $\D\pr=\D
{P\uni\set{q}}$ that is not in $\D=\D
P$ is incident to $q$. Any edge of $\D$ that is not in $\D\pr$ connects two sites that are neighbors of $q$ in $\D\pr$.\fig3}

\mfig7
\proof{Let $e$ be an edge of $\D\pr$ with both endpoints in $P$. Consider the $P\pr$-free circle $C$ that proves $e$ is in $\D\pr$; that circle is obviously $P$-free, and proves that $e$ is in $\D$. Therefore, an edge that is in $\D\pr$ but not in $\D$ must be incident to $q$.

\pp Now let $e$ be an edge of $\D$ that is not in $\D\pr$. Let $u$ and $v$ be its endpoints, and let $C$ be the $P$-free circle that proves $e$ is in $\D$. Since $e$ is not in $\D\pr$, $C$ cannot be $P\pr$-free, that is, $q$ must be inside $C$. Then consider the circle $C\pr
u$ that lies inside $C$, is tangent to it at $u$, and  passes through $q$. This circle proves $uq$ is an edge of $\D\pr$. The proof for $v$ is analogous.}
\endmfig

Lemma \Th{49} shows that the relation between $\D$ and $\D\pr$ is rather simple. If $p
1, p
2, \ldots, p
m$ are the neighbors of $q$ in $\D\pr$, then the edges $qp
i$ will be the only new ones in $\D\pr$, and the edges that have to be deleted from $\D$ (if any) are connecting two of the $p
i$.\fig4

A similar observation holds also for Delaunay triangulations:

\lemma{\Th{49A}}{If $\DT$ is a Delaunay triangulation of $P$, then there is a Delaunay triangulation $\DT\pr$ of $P$ such that

\tp (1) every edge of $\DT\pr$ that is not in $\DT$ is incident to $q$, and

\tp (2) the endpoints of every edge of $\DT$ that is not in $D\pr$ are neighbors of $q$ in $\DT\pr$.}

We will prove this lemma by exhibiting an algorithm that constructs $\DT\pr$ from $\DT$.

\subsection{JUNK: BEGIN}

In practice, we may want to take the triangulation of the Delaunay diagram one step further, by adding three dummy sites $\pi
1, \pi
2, \pi
3$ such that all other sites are well within the triangle with those vertices. \fig4
If those dummy sites are sufficiently far away, all edges and internal faces of $\D
P$ will be also edges and faces of $\D
{P\uni \set{\pi
1, \pi
2, \pi
3}}$, but {\it all} faces of the latter (including the exterior one) will be triangles. This avoids having special code for dealing with the outer face, and can even lead to a simplification of the data structure. On th other hand, this extension is somewhat incompatible with some of the algorithms we will see later on, so we will introduce it on a case-by-case basis, and always state it explicitly. 

\footprob{\Prob{\Sbsec{\Sec1.7}.1}}{(a) Give a data structure for triangulations of a manifold that uses less pointers per edge that the quad-edge data structure, which allows $\sym$, $\onext$, $\rot$, and $\oprev$ in constant time. Be careful to preserve uniformity between dual and primal.\bxpar
{\it Ans.}: Keep only one record $\onext$ for a primal edge and its $\sym$, and represent directed edges as pairs (edge record, rot exponent). To get $\onext$ of dual edges, use the identity $e\rot\onext=e\sym\onext\sym\onext\rot$, valid in triangulations.}

\subsection{END JUNK.}

To simplify the algorithm, we will assume $P$ includes three dummy sites $w
0, w
1, w
2$ such that the triangle $w
0w
1w
2$ contains $q$ and all other ``normal'' sites of $P$. Furthermore, we will assume these dummy sites are so far away that they do not ``interfere'' with the normal ones. That is, the Delaunay diagram of $P-\set{w
0, w
1, w
2}$ is a subgraph of $\D
P$, and every internal face of the former is an internal face of the latter. In other words, $\D
P$ consists of $\D
{P-\set{w
0, w
1, w
2}}$ surrounded by the triangle $w
0w
1w
2$, with the space between the two subdivided into traingular faces.\fig4

\xx{Do we need this trick in other algorithms? if no, then remove the previous mention of it, and merge it here.}

\xx{Better do without this trick. Add the following proviso to the algorithm: if $q$ is not in any interior face, connect it to all visible vertices of the outer face.}

To satisfy this property, the dummy sites must lie outside the circumcircle of the every internal face of $\D
P$. Unfortunately, the problem of finding three points with those properties seems as hard as computing the Delaunay itself: in particular, there seems to be no simple upper bound to the radius of those circumcircles. To get around this problem, we must resort to a trick: we must consider these points to lie at ``practically infinite distance'' in appropriate directions. More specifically, we will consider $w
0$, $w
1$ and $w
2$ to lie at infinite distance from the origin, respectively at $0\deg$, $120\deg$ and $240\deg$ from the $x$-axis.\fig3

This requires we extend our definitions of Delaunay diagrams and triangulations to allow for such ``infinitely remote'' sites. A mathematically precise definition would be too long to be worthwhile, so we will limit ourselves to a semi-intuitive interpretation. We will define a geometric concept (edge, face, circumcircle, triangulation, etc) involving dummy sites by a limiting process, where each $w
i$ is replaced by a finite point that is moved towards infinity in the corresponding direction. For example, the interior of the circle passing through $w
0$ and two normal sites $r, s$ (with $y
r<y
s$) is the right half-plane of  the straight line $rs$, when oriented from $r$ to $s$. This half-plane is the limit of the circle $rsw
0$ when $w
0$ moves towards infinity along the $x$-axis from a finite position.

Clearly, this method does not every time: the limiting object may not exist, or may not be unique. For example, the circle passing through $w
0$, $w
1$ and a normal site $p$ can be the right half-plane of any straight line passing through $p$ and making with the $x$-axis any angle between $120\deg$ and $180\deg$, depending on the relative speed with which $w
0$ and $w
1$ go to infinity. Therefore, we must exercise some case when talking about such objects.

Nevertheless,we still can define a Delaunay triangulation of $P$ by means of theorem \Th{15}: it is a triangulation $\DT$ of $P$ in which every interior face has a (possibly degenerate) $P$-free circumcircle.\fig5
A careful analysys of the degenerate cases shows that lemmata \Th{??} and \Th{??} also remain valid: A triangulation of $P$ is a Delaunay one if and only if every edge that is not on the exterior face satisfies the angle property \xx{define it}; and the edges of the Delaunay diagram satisfy it with strict inequality.

Before proceeding, let us check that such a subdivision does indeed contain a complete Delaunay triangulation of the normal sites. The outer face of such a triangulation is the exterior of the triangle $w
0w
1w
2$, and so it lies completely ``out of sight''. If there are no normal sites, then the only interior face is the interior of the triangle $w
0w
1w
2$. Otherwise, every interior face $F$ of $\DT$ is incident to at least one normal site. If $F$ is incident to one or two dummy sites, the $P$-free circumcircle establishing the ``Delaunayhood'' of $F$ degenerates to an half-plane, and all normal sites of $P$ will lie on the complementary half-plane. This means $F$ is completely outside the convex hull of the normal sites. With a little more argument it follows that the the interior faces of $\DT$ whose vertices are all normal, plus their edges and vertices, constitute a triangulation of the normal sites with convex outer boundary. Since those faces have $P$-free circumcircles, they constitute a Delaunay triangulation of $P-\set{w
0, w
1, w
2}$. 

\xx{This trick is quite dirty. The dummy sites are not the point at infinity $\omega$, since the latter is unique in the extended plane. We cannot use the projective plane, for we must distinguish the two sides of a straight line, and also the point $(+\infinity, 0)$ from $(-\infinity, 0)$.

Ahem! On the 2SP, however...}

Let then $P$ be a collection of sites augmented with the dummy sites as explained above, and let $q$ be a normal site not in $P$. The algorithm below modifies a Delaunay triangulation $\DT$ for $P$ so that the resulting graph $\DT\pr$ is a Delaunay triangulation of $P\pr=P\uni\set{q}$. For simplicity, we will assume $q$ does not lie on any edge of $\DT$. The handling of such exceptional cases is a trivial exercise.

\footprob{\Prob{\Sbsec{\Sec2.3}.1}}{Modify algorithm \Alg1 so that it handles properly the case where $q$ lies on an edge $e$ of $\DT$. {\it Ans.}: If this happens in step \Step1, delete $e$ and connect $q$ to the four vertices of the quadrilateral defined by it. That is all.}   

\algorithm{\Alg1}{Insert a new site $q$ in a Delaunay triangulation $\DT$.}{
\begblock
  \comm{The algorithm uses a stack $S$, initally empty, whose entries
    are directed edges of the original triangulation. for simplicity}
  \step{\sno{\Step1} Locate a face of $\DT$ that contains
    $q$, and let $rst$ be its vertices (in counterclockwise order).
    Connect $q$ to $r$, $s$ and $t$ by new edges, and
    push the directed edges $rs$, $st$, and $tr$ into $S$.}
  \step{\sno{\Step2} While $S$ is not empty, do:}
  \begblock
    \step{\sno{\Step3} Remove the topmost edge $e$ from $S$; let
      $u$ be its origin and and $v$ be its destination.}
    \step{\sno{\Step4} If $u$ and $v$ are both dummy vertices,
      go back to step \Step2.}
    \comm {At this point the left face of $e$ will be the triangle $quv$,
      and the right face will be $pvu$ for some site $p\in P$.}
    \step{\sno{\Step5} If $p$ is dummy, or $e$ satisfies the angle
      property, go back to step \Step2.}
    \step{\sno{\Step5} Delete the edge $e$ from the triangulation,
      and add to it the edge $qp$. Push the edges $up$ and $pv$
      onto the stack $S$.}
    \step{\nono Repeat from step 2.}
  \endblock
\endblock}

\xx{Informal description of the algorithm}

\subsection{\bf JUNK BEGIN}

However, the edges of the enclosing triangle are themselves suspect. We can remove suspect edges by the swapping rule discussed in section 8. This gives rise to a very simple algorithm, given in high-level form below.

At any one time the set of triangles with the new point $X$ as a vertex form a star-shaped polygon around $X$. This is because the polygon can only get larger with each application of the swap rule on a bounding edge, and if it does grow, then the two new stacked sides are in the angular sector with vertex $X$ and delimited by the deleted edge. Furthermore, because we stack edges in a consistent order, the stacked edges always form a contiguous section of the perimeter of that polygon, with the rest of the perimeter consisiting of the forgotten edges.

\subsection{\bf END JUNK.}

\lemma{\Th60}}{Every time we get to step \Step2,

\tp 1. The graph is a triangulation;

\tp 2. Every edge that was not in $\DT$ is incident to $q$;

\tp 3  Every edge $e=uv$ on the stack has $uvq$ as its left face;

\tp 4. Every edge that is not on the stack satisfies the angle property.}

\proof{{\bf BEGIN JUNK:} The circumcircle $C$ of the face $rst$ is $P$-free. Now consider the circle $C
r$ that passes through $q$ and is tangent to $C$ internally at $r$. This circle is $P\pr$-free and has $qr$ as a chord, which by theorem \Th{8C} proves $qr$ is an edge of $\D
{p\pr}$. Note that a suitable circle $C
r$ can be constructed even if some or all of the vertices of $rst$ are dummy. The same arguments works for $qs$ and $qt$.

\pp {\bf MORE JUNK:} All edges incident to the new point introduced during applications of the swap rule in the above algorithm are Delaunay edges. So is each forgotten edge. PROOF: Let $X$ be the new point and suppose that the swap rule was just applied to quadrilateral $XLMN$ where it replaced diagonal $LN$ with diagonal $XM$, as in fig. 10.2, Then  $X$ must be interior to the circle $LMN$ and by the same argument as in the proof of lemma 10.1 it follows that $XM$ is a Delaunay edge. If the swap rule failed on $XLMN$, then $X$ is outside the circle $LMN$, and so edge $LN$ is Delaunay and can be forgotten.

\pp {\bf MORE JUNK:} From lemma 10.2 we know that all edges leading to the new point $X$ and introduced during the above algorithm are Delaunay edges. The only other edges bounding new triangles are the edges of the star-shaped polygon discussed in the proof of lemma 10.3. At the termination of the loop the stack is empty and so all the bounding edges have been forgotten at some point. Thus there are no suspect edges left.

\pp {\bf END JUNK}}

\xx{conclude the correctness of the algorithm}

\subsection{\bf JUNK BEGIN}

When the above loop terminates the swap test fails everywhere in the triangulation.

\lemma{10.3}{No edge is ever stacked twice.}

\proof{One of two things can happen at each application of the swapping rule. If the swap succeeds, then the polygon grows past the old bounding edge, so that edge can never be on its boundary again. If it fails, then that bounding edge is frozen and the algorithm will never again touch any edge in the angular sector with vertex $X$ and delimited by that edge.}

The above lemmas imply that this loop correctly computes the final Delaunay triangulation, and that it does so in at most $O(n)$ time. More precisely, if $k$ edges need to be added or deleted to update the Delaunay structure, then our algorithm works in time $O(k)$, since each edge added by the algorithm must be added, and each edge that is deleted must be deleted.

\subsection{\bf END JUNK}

\xx{Simplifications on this algorithm:}

\subsection{\bf JUNK BEGIN}

We saw that the forgotten edges will always define a path around the new point, which will eventually close. If $e$ is an edge on the path, then the next edge is $e\ \lnext\ \oprev$. This observation gives us a way to implement the above algorithm without any auxiliary storage, such as the stack, by a method that is similar to that used in the previous section. Here {\basel} starts out (arbitrarily) as one of the edges connecting the new point to one of the vertices of its enclosing triangle. By convention we think of the new point as being the left end point of {\basel}. Then {\lcand} will always be invalid (non-existent, in fact) and we will consider for {\rcand} the various edges out of the other endpoint of {\basel}. The successively found {\rcand}$\,$s, as we proceed counterclockwise around the new point, will correspond to the forgotten edges of the previous algorithm. Note, however, that the incremental algorithm connects ahead'' after each deletion, while the algorithm of the previous section would connect all cross edges in strict counterclockwise order.

\subsection{\bf END JUNK}

\xx{Using this algorithm to build the Delaunauy from scratch.}

\xx{Using this algorithm on-line}

The $\CCW$ predicate, that tests whether three points of $\reals↑2$ define a counterclockwise oriented triangle, is the two-dimensional instance of a more general predicate describing the orientation of $k+1$ points of $\reals↑k$. This general predicate will be better understood if we focus our attention first upon the three-dimensional case.  

\definition{\Def{37}}{We say that four points $a,b,c$, and $d$ of $\reals↑3$ (in that order) are {\it positively} (resp. {\it negatively}) {\it oriented} if they are not coplanar and the triangle $abc$ is counterclockwise (resp. clockwise) oriented as seen from $d$. We denote these conditions by $\posor(a,b,c,d)$ and $\negor(a,b,c,d)$, respectively.}

By ``counterclockwise oriented as seen from $d$'' we mean that the three vectors $a-d$, $b-d$, and $c-d$, in that order, constitute a right-handed basis. That is, the determinant
$$\det{\matrix3{
    x
a-x
dy
a-y
dz
a-z
d\cr\va
    x
b-x
dy
b-y
dz
b-z
d\cr\va
    x
c-x
dy
c-y
dz
c-z
d\cr}}\eqno(\Eq{37})$$
of the linear transformation mapping the standard basis into those three vectors is positive. Similarly, the points are clockwise oriented as seen from $d$ if the determinant (\Eq{37}) is negative. \xx{Is there a more natural definition of ``counterclockwise oriented as seen from $d$'' such that the determinant (\Eq{37}) follows easily?} 

The theorem below gives a fundamental property of these predicates:

\theorem{\Th{48}}{The points $a,b,c$, and $d$ of $\reals↑3$, in that order, are positively oriented, coplanar, or negatively oriented, depending on whether the determinant
$$\Delta(a,b,c,d)=\det{\matrix4{
    x
ay
az
a1\cr\va
    x
by
bz
b1\cr\va
    x
cy
cz
c1\cr\va
    x
dy
dz
d1\cr}}\eqno(\Eq{38})$$
is positive, zero, or negative, respectively.}

\proof{The four points are coplanar if and only if the three vectors $a-d$, $b-d$ and $c-d$ are linearly dependent. Since these vectors are the rows of (\Eq{37}), this happens if and only if that determinant is zero. We conclude that the four points are positively oriented, coplanar, or negatively oriented, depending on whether (\Eq{37}) is positive, zero, or negative.

\pp Now consider the determinant $\Delta(a,b,c,d)$ above. If we subtract the fourth line from the other three, we get
$$\Delta(a,b,c,d)=\det{\matrix4{
    x
a-x
dy
a-y
dz
a-z
d0\cr\va
    x
b-x
dy
b-y
dz
b-z
d0\cr\va
    x
c-x
dy
c-y
dz
c-z
d0\cr\va
    x
dy
dz
d1\cr}},\eqno(\Eq{39})$$
which gives (\Eq{37}) when expanded by the fourth column. This concludes the proof.}

\xx{Remark on best ways to compute $\posor$; give code?}

We remark in passing that the volume of the tetrahedron with vertices $a$, $b$, $c$ , and $d$ is ${1\over6}\leftv\Delta(a,b,c,d)\rightv$. The following properties of $\posor$ and $\negor$ folow immediately from theorem \Th{48} and the properties of determinants:

\theorem{\Th{49}}{Let $a\pr$, $b\pr$, $c\pr$, and $d\pr$ be any permutation of the four points $a, b, c$, and $d$ of $\reals↑3$. Then $\posor(a\pr, b\pr, c\pr, d\pr)$ is the equivalent to $\posor(a,b,c,d)$ or $\negor(a,b,c,d)$, depending on whether the permutation is even or odd, respectively. In particular, $$\posor(a,b,c,d)\equiv\negor(b,c,d,a)\equiv\posor(c,d,a,b)\equiv\negor(d,a,b,c)$$}

\xx{Generalize to higher dimensions}

\xx{Perhaps it is wiser to use the terms ``positively oriented'' instead of ``counterclockwise oriented'' for the planar case too. I think it sounds better, and it makes the notation more uniform.}

\subsection{\Ch8.\Sbsec{\Sec2.2}. Oriented planes}

\xx{For compatibility with higher dimensions, the orientation of a line should be given by a normal vector. What about circles??? Worry about this in the 2SP.}

The concept of oriented line extends quite naturally to Euclidean spaces of more than two dimensions. In the three-dimensioanl space $\reals↑3$, we define an {\it oriented plane} $\pi$ as a plane (in the classical sense) endowed with a {\it normal direction} $\hat \pi$, a unit vector perpendicular to it. We are therefore able to distinguish the {\it left half-space} of $\pi$, into which $\hat \pi$ points, from its {\it right half-space}. The {\it signed distance} from $\pi$ to an arbitrary point $p$, denoted by $\sdist(\pi, p)$, is the usual Euclidean distance between the two (measured perpendicularly to $\pi$) taken with plus or minus sign depending on whether $p$ lies in the left or right side of $\pi$. Obviously, the signed distance is zero if and only if $p$ lies on $\pi$. 

An oriented plane can be algebraically specified by a quadruple of real coefficients $X,Y,Z$, and $W$, such that not all three of $X, Y$, and $Z$ are zero. By definition, a point $p=(x, y, z)$ is on the plane, to its left, or to its right depending on whether the expression $X x+Y y+Z z+W$ is zero, positive, or negative, respectively. It is easy to prove that such an oriented plane $\pi$ exists and is unique; we will denote it by $\plc{X, Y, Z\hom W}$. \xx{The justification for this notation is by analogy with homogeneous coordinates of a point, $[x,y,z\hom w]$.} Its unit normal vector is
$$\hat\pi={1\over{\sqrt{X↑2+Y↑2+Z↑2}}}\,(X, Y, Z),\eqno(\Eq{92})$$
and passes through the point 
$$\pi
0=-{W\over{X↑2+Y↑2+Z↑2}}\,(X, Y, Z).\eqno(\Eq{93})$$
The signed distance from $\pi$ to an arbitrary point $p=(x,y,z)$ is then the difference between the components of $p$ and $\pi
0$ along the normal direction $\hat\pi$, that is,
$$\sdist(\pi, p)={{Xx+Yy+Zz+W}\over{\sqrt{X↑2+Y↑2+Z↑2}}}.\eqno(\Eq{94})$$
In particular, the signed distance from $\pi$ to the origin is
$$\sdist(\pi, O)={W\over{\sqrt{X↑2+Y↑2+Z↑2}}}.$$

When $X↑2+Y↑2+Z↑2=1$, the coefficients are said to be {\it normalized}, and the formulas above simplify to
$$\eqalign{\hat\pi=(X, Y, Z),\cr\vb
    \pi
0=(-WX, -WY, -WZ),\cr\vb
    \sdist(\pi, p)=Xx+Yy+Zz+W,\cr\vb
\noalign{\hbox{and}}\vb
    \sdist(\pi, O)=W.\cr}$$
It is easy to prove that $\plc{X, Y, Z\hom W}$ and $\plc{X\pr, Y\pr, Z\pr\hom W\pr}$ denote the same oriented plane if and only there is a {\it positive} real number $\alpha$ such that $X=\alpha X\pr$, $Y=\alpha Y\pr$, $Z=\alpha Z\pr$, and $W=\alpha W\pr$. It follows that every oriented plane has a unique set of normalized coefficients. The oriented plane $\plc{-X, -Y, -Z\hom -W}$ passes through the same points as $\plc{X, Y, Z\hom W}$, but has the opposite orientation: the left half-space of one is the right half-space of the other, and vice-versa. 

\footprob{\Prob{\Sbsec{\Sec1.1A}.1}}{When and where does the plane $\pi=\plc{X, Y, Z\hom W}$ intersect the three coordinate axes?}

\footprob{\Prob{\Sbsec{\Sec1.1A}.2}}{What is the relationship between $\plc{X, Y, Z\hom W}$ and $\plc{X, Y, Z\hom -W}$?}

\footprob{\Prob{\Sbsec{\Sec1.1A}.3}}{Generalize oriented plane and related concepts to higher dimensions}

\xx{Develop the analogous theory for points in homogenous coordinates}

\xx{Find the best format for the theorem below: define $\plane$ formally first, and then prove the validity? what can be put in prose?}

\theorem{\Th{51}}{For any three non-colinear points $a, b$, and $c$ of $\reals↑3$, there is a unique oriented plane passing through them such that a point $d$ lies on its left half-space if and only if the points $a,b,c,$ and $d$ are positively oriented.}

\proof{If we expand the determinant (\Eq{38}) of theorem\Th{48} by its last row, we get
$$\Delta(a,b,c,d)=Xx
d+Yy
d+Zz
d+W,\eqno(\Eq{51})$$
where
$$\eqalign{
  X=-\det{\matrix3{
    y
az
a1\cr
    y
bz
b1\cr
    y
cz
c1\cr}},\cr\vc
  Y=+\det{\matrix3{
    x
az
a1\cr
    x
bz
b1\cr
    x
cz
c1\cr}},\cr\vc
  Z=-\det{\matrix3{
    x
ay
a1\cr
    x
by
b1\cr
    x
cy
c1\cr}},\cr\vb
\noalign{\hbox{\ and}}\cr\vb
  W=+\det{\matrix3{
    x
ay
az
a\cr
    x
by
bz
b\cr
    x
cy
cz
c\cr}}.\cr}\eqno(\Eq{52})$$

\pp Note that $X$, $Y$, $Z$, and $W$ do not depend on the point $d$. By theorem \Th{48}, expression (\Eq{51}) is zero when $d=a$. On the other hand, since $a,b$, and $c$ are not colinear, there is some point $d$ that is not coplanar with them, and therefore makes (\Eq{51}) nonzero. It follows that not all three of $X$, $Y$ and $Z$ are zero, so $\plc{X,Y,Z\hom W}$ are the coefficients of an oriented plane. By (\Eq{51}) and theorem \Th{48}, this plane has the required property.

\pp \xx{prove that it is unique}}

\definition{\Def{51}}{Given three non-colinear points $a,b,$ and $c$ of $\reals↑3$, we denote by $\plane(a, b, c)$ the oriented plane passing through them and oriented so that the triangle $abc$ is counterclockwise oriented when seen from any point on the left half-space}

 In the algorithms we are going to see, the arguments of $\incircle$ will be always sites of $P$. Threfore, it is better to precompute and store the quantity $z
{\lambda(a)}=x
a↑2+y
a↑2$ for every site $a$ at the beginning of the algorithm.Then each $\incircle$ test reduces to the computation of a $4\times 4$ determinant like (\Eq6)
 
\xx{move this to preceding section:} Notice that this establishes an interesting correspondance between circular queries in the plane and half-space queries in 3-space.

\xx{Edit this:} In particular, if $a$, $b$, and $c$ are not collinear, and the triangle $abc$ is counterclockwise oriented, then $\incircle(a, b, c, d)$ is true whenever $d$ lies inside the circle $abc$. If $abc$ is clockwise oriented, the meaning is reversed: $\incircle(a, b, c, d)$ is true whenever $d$ is {\it outside} the circle $abc$. If $a$, $b$, and $c$ lie on the same line $\lscr$, then the predicate tests whether $d$ is on the left half-plane of $\lscr$, when the latter is oriented from $a$ through $b$ to $c$. The predicate is false if any two points are coincident, or if $a, b, c$, and $d$ all lie on the same circle.\fig4

{\bf JUNK:} Notice that the test is equivalent to asking whether $\angle ABC + \angle CDA >\angle BCD + \angle DAB$.

\xx{The following should really be a discussion of the properties of the ``positively oriented'' predicate.}

The $\incircle$ test possesses several interesting properties:

\lemma{\Th{44}}{If $a$, $b$, $c$, $d$ are any four non-cocircular points in the plane, then transposing any adjacent pair in the predicate $\incircle(a,b,c,d)$ will change the value of the predicate from true to false, or vice versa.}

\proof{This is obvious from theorem \Th{43} and the properties of determinants.}

In particular, the boolean sequence $\incircle(a,b,c,d)$, $\incircle(b,c,d,a)$, $\incircle(c,d,a,b)$, $\incircle(d,a,b,c)$ is either T(rue), F(alse), T, F, or F, T, F, T. More generally, permuting the arguments of $\incircle(a,b,c,d)$ will either preserve or reverse its value, depending on whether the permutation has even or odd parity. However, the predicate $\incircle$ is always false if the four points are cocircular, independently of their order.

By theorem \Th{15}, the first one is a Delaunay triangulation if and only if the circles $abc$ and $cda$ are both $P$-free, that is, $\incircle(a,b,c,d)$ and $\incircle(c,d,a,b)$ are both false. From the properties of $\incircle$ we know these two are equivalent, and also they are equivalent to $\outcircle is not inside the circle $abc$, and $b$ is not inside the circle $cda$. Now consider the arcs subtended by the internal angles $\hat a, \hat b, \hat c, \hat d$ of $Q$ on the circle $abc$. Its is clear that $d$ will be on or outside that circle if and only if the arcs subtended by $\hat a$ and $\hat c$ add to $360\deg$ or more, that is, $\hat a+\hat c \geq 180\deg$.\fig3
Since the internal angles of any quadrilateral add up to $360\deg$, this condition is equivalent to $\hat b+\hat d \leq 180\deg$. By symmetry, the {\it second} diagram above is a Delaunay triangulation when $\hat b+\hat d \geq 180\deg$, or equivalently when $\hat a+\hat c \leq 180\deg$. In the limiting case when $\hat a+\hat c = 180\deg=\hat b+\hat d$, all four points lie on the same circle, and both triangulations are Delaunay. We conclude that in either Delaunay triangulation of $P$, the diagonal edge $pq$ used in it has the property that the internal angles $\hat p$ and $\hat q$ of $Q$ add to at least $180\deg$, or equivalently only that the other two angles $\hat r$ and $\hat s$ add to at most $180\deg$.

If $prq$ and $qsp$ are the vertices (in counterclockwise order) of two adjacent interior faces of a triangulation, we say that $p,r, q$, and $s$ (in that order) are the vertices of the {\it edge quadrilateral} corresponding to $pq$.\fig3   

\lemma{\Th{20}}{Let $e=pq$ be an edge of a triangulation with edge quadrilateral $prqs$. The following affirmations are all equivalent:

\tp 1. $\hat p+\hat q \geq 180\deg$;

\tp 2. $\hat s+\hat r \leq 180\deg$;

\tp 3. $r$ is not inside the circle $pqs$;

\tp 4. $s$ is not inside the circle $prq$;

\tp 5. $\hat p \geq 180$, or $q$ is inside the circle $spr$;

\tp 6. $\hat q \geq 180$, or $p$ is inside the circle $rqs$.

\tp 7. There is a circle through $p$ and $q$ such that neither $r$ nor $s$ lies inside it.

\tp 8. There is no circle through $r$ and $s$ such that both $p$ and $q$ lie outside it.}

\proof{

\pp Now assume $\incircle(a,b,c,d)$, and consider the circle $C\pr$ tangent internally to $C$ at $b$ and passing through $d$. This circle touches $C$ only at $b$, and therefore $a$ and $c$ lie outside it, proving condition 4.\fig3

\pp Conversely, assume there a circle $C\pr$ through $b$ and $d$ such that $a$ and $c$ are both outside it.???}

Let $P$ consist of four sites $a,b,c,d$, defining in this order the vertices of a convex quadrilateral $Q$. This set admits of only two triangulations, consisting of the exterior edges $ab$, $bc$, $cd$, and $da$, and one of the two diagonals $ac$ or $bd$:\fig3

From the properties of $\incircle$, we know that
$$\incircle(a,b,c,d)=\outcircle(b,c,d,a)=\incircle(c,d,a,b)=\outcircle(d,a,b,c).$$
Since $a,b,c,d$ are listed in counterclockwise order around $Q$, the circles $abc$, $bcd$, $cda$, and $dab$ are all counterclockwise oriented. So, all four tests above have their ``natural'' interpretations. That is, $\incircle(a,b,c,d)$ is true if and only if $d$ is interior to the circle $abc$, and so forth.

Now, if $\incircle(a,b,c,d)$ is false, the circle $abc$ is $P$-free; by the identities above, the same will be true of the circle $cda$, and the triangulation using the diagonal $bd$ will be a Delaunay one. Similarly, if the circle $bcd$ is $P$-free, the same will be true of the circle $dab$, and the triangulation using $ac$ will be Delaunay. In the limiting case where all four points are cocircular, the four circles coincide and are $P$-free, so either diagonal will give a Delaunay triangulation.

Now consider the internal angles $\hat a, \hat b, \hat c,\hatd$ of the quadrilateral $Q$. By lemma \Th{20C}, $\incircle (a,b,c,d)$ is false if and only if $\hat a+\hat c \geq 180\deg$, or equivalently $\hat b+\hat d \leq 180\deg$. Conversely, $\incircle (b,c,d,a)$ is false if and only if $\hat b+\hat d \geq 180\deg$, or equivalently $\hat a+\hat c \leq 180\deg$. The discussion above then can be restated as follows: {\it a Delaunay triangulation of the vertices of $Q$ must use the diagonal of $Q$   connecting the two opposite internal angles with largest sum}. These are also the two opposite angles adding up to $180\deg$ or more. 

This rule works also if $Q$ is simple but not convex. Such a quadilateral has exactly one interior angle that is larger than $180\deg$; according to the rule above, a Delaunay triangulation of its vertices should use the diagonal connecting this vertex to the opposite one. Actually, in this case the only triangulation of those four sites uses {\it both} diagonals of $Q$, in addition to its four sides.\fig3  

We will now extend this discussion to Delaunay triangulations of more than four vertices.

\definition{\Def{12}}{Let $e=pq$ be an interior edge of a triangulation, and let $Q=prqs$ be its edge quadrilateral. We say that $e$ satisfies the {\it angle property} if it connects the opposite angles of $Q$ having largest possible sum, that is, if $\hat p+\hat q \geq \hat s+\hat r$.}

\lemma{\Th{21}}{Any edge of $\D
P$ not on the exterior face satisfies the strict angle property in any triangulation of $P$ that uses it.}

\footprob{\Prob{\Sbsec{\Sec1.9}.3}}{Let us define a {\it $C$-subdivision} as a convex subdivision of the plane with convex outer boundary and such that all vertices of each interior face $F$ lie on a common circle $C
F$. Clearly, every Delaunay diagram is a $C$-subdivison. (a) Exhibit a $C$-subdivision that is not a Delaunay diagram. (b) Write an algorithm that tests whether a quad-edge data structure represents a $C$-subdivision. (c) Extend the angle property to $C$-subdivisions, as follows: we say that an edge $e=pq$ of a $C$-subdivision, with left and right faces $F$ and $G$, satisfies the strict angle property if the internal angles at $p$ and $q$ of the polygon $F\uni G$ add up to more than $180\deg$. Prove that this is the same as saying that no vertices of $F$ lie on or inside $C
G$, or equivalently that no vertices of $G$ lie on or inside $C
F$. (d) Prove that a $C$-subdivision is a Delaunay diagram if and only if every edge in it satisfies the strict angle property. (e) Write an algorithm that tests whether a $C$-subdivision a Delaunay diagram.}

\lemma{\Th{20D}}{Any edge $e$ of an arbitrary Delaunay triangulation of $P$ that does not satisfy the angle property cannot be an edge fails the angle As in the introdutory discussion, properties 4 and 5 imply that $e$ could be used in a Delaunay triangulation {\it if we considered only the four vertices $p,q,r,s$}. When all sites are considered, however, there may exist {\it no} Delaunay triangulation containing $e$:\fig3

\lemma{\Th{19}}{A triangulation $T$ of $P$ is a Delaunay triangulation if and only if every interior edge of $T$ has the angle property.}

\proof{Let us assume $S$ is a Delaunay triangulation, and $Q=prqs$ is any of its edge quadrilaterals. By lemma \Th{15}, there is a $P$-free circle $C$ circumscribed around the face $prq$. Let $o$ be any point of $pq$; since $o$ is interior to $C$ and $s$ is not, the (closed) segement $os$ must intersect the boundary of $C$ at some point $s\pr$. It is clear that $s\pr$ will be separated from $r$ by the line of $pq$.\fig3
The arcs subtended on $C$ by the inscribed angles $\angle s\pr pr$ and $\angle rqs\pr$ add to $360\deg$, so the angles themselves add to $180\deg$. Since $s\pr$ lies inside (or on the boundary of) the triangle $qsp$, the internal angles $\hat p=\angle spr$ and $\hat q=\angle rqs$ of $Q$ are greater than or equal to $\angle s\pr pr$ and $\angle rqs\pr$, respectively. It follows that $\hat p + \hat q\geq 180\deg$.

\pp In the same way, we conclude that $\angle qs\pr p + \angle prq=180\deg$, and that in $Q$ the internal angle $\hat s=\angle qsp$ is less than or equal to $\angle qs\pr p$, so $\hat r+\hat s\leq 180\deg$.

\pp \xx{What about the ``if'' part?}}

\lemma{\Th{20D}}{Any edge $e$ of an arbitrary Delaunay triangulation of $P$ that does not satisfy the angle property cannot be an edge fails the angle if $e$ fails the angle test, then it cannot possibly be an edge of any Delaunay triangulation:

\xx{mumble some about Delaunay of four sites (angle test is equivalent to considering the Delaunay of the vertices of the edge quadrilateral)}

\proof{Form what we saw in chapter \Ch3 \xx{(let's pretend so)} we know that $\hull(\lambda(K))$ is a facet of $\hull(\lambda(P))=\H$ if and only if there is an oriented plane $\pi$ passing through all points of $\lambda(K)$, and all other points of $\lambda(P)$ lie either in the interior of $\hull(\lambda(K))$ or strictly on one particular side of $\pi$. Because of the strict concavity of the paraboloid $\Lambda$, $\hull(\lambda(K))$ cannot contain any point of $\lambda(P)$ other than those in $\lambda(K)$, and all of the latter are vertices of $\hull(\lambda(K))$. So, the points in $\lambda(K)$ are the vertices of a facet of $\H$ if and only if there is an oriented plane $\pi$ passing through all points of $\lambda(K)$, and all other points of $\lambda(P)$ lie on one particular side of $\pi$.

Now, from lemmas \Th{13}, \Th{16}, and \Th{17} it follows that $\D
P K$ is nonempty if and only if there is a plane $\pi$ passing through the points $\lambda(K)$ and strictly below the other points of $\lambda(P)$. Th theorem then folows.}   

In other words, the Delaunay diagram of a set $P$ is isomorphic to the ``underside'' of the three-dimensional convex hull of $\lambda(P)$! In fact, every edge and face of the Delaunay is the projection on the $(x, y)$ plane of a edge or face of that hull that is visible from below.

\par\vfill\eject\end