\def\E{\Escr} % \E(p,q), \E K = Bisector of p and q (resp K)
\def\C{\Cscr} % \C(p,q) = Locus of points closer to p than to q
\def\V{\Vscr} % \V
P = Voronoi of P, \V
P K = region of it def. by K
\def\D{\Dscr} % \D
P = Delaunay of P, \D
P K = region of it def. by K
\def\T{\Tscr} % \T
P = A Delaunay triangulation
\def\L{\Lscr} % The lower portion of \hull{\Lambda(P)}
\def\H{\Hscr} % A convex hull
\def\F{\Fscr} % A facet of a convex hull. Maybe should use F instead.

\def\plc#1{{\langle #1 \rangle}} % \plc{X,Y,Z\hom W} = Plane Xx+Yy+Zz+W=0.
\def\hom{\relvv } % Separates weight in homogeneous coordinates.

\def\posor{\mathop{\char P\char O\char S}}
\def\negor{\mathop{\char N\char E\char G}}
\def\plane{\mathop{\char p\char l\char a\char n\char e}}
\def\circle{\mathop{\char c\char i\char r\char c\char l\char e}}
\def\outcircle{\mathop{\char O\char u\char t\char C\char i\char r\char c\char l\char e}}

\def\base{{$e$}}
\def\newbase{{$e\pr$}}
\def\root{{$\mathop{\char r \char o\char o\char t}$}}

\def\Sham{Sh}
\def\Kirki{Ki1}
\def\Kirkii{Ki2}
\def\ShamHo{SH}
\def\GuiSto{GuiSto}
\def
\GrSi{GS}
\def\Baum{Ba}
\def\Braid{Br}
\def\IyKa{IK}
\def\MuPr{MP}
\def\MaSu{MS}
\def\Kle{Kel}
\def\Knuth{Kn}
\def\Even{Ev}
\def\Lee{Le}
\def\Har{Har}
\def\PH{PH}
\def\Sei{Sei}

\def\lcand{\hbox{\it lcand}}
\def\rcand{\hbox{\it rcand}}
\def\basel{\hbox{\it basel}}
\def\ldi{\hbox{\it ldi}}
\def\rdi{\hbox{\it rdi}}

$$\eqalign{C(p, q)=\rset{x\in\Sscr\relv\dist(x, p)<\dist(x, q)}\cr
E(p,q)=\rset{x\in\Sscr\relv\dist(x, p)=\dist(x, q)}.\cr}$$

\theorem{\Th{32}}{Let $P$ is a finite set of points of an Euclidean space $\Sscr$. For any site $p\in P$, $V
P(p)$ is a $k$-dimensional open convex polytope.}

\proof{According to lemma \Th1, the Voronoi region $V(p)$ is the (non-empty) intersection of a finite number of half-spaces $C(p, q)$, and therefore is a convex polytope by definition \Ch3.\Def?\foot\dag{\bf Not there yet.}. Since each $C(p,q)$ is an open set, the same is true of $V(p)$.}

These properties can be proved by generalizing theorems \Th1 and \Th2:

\lemma{\Th33}{For any nonempty subset $K$ of $P$,
$$V
P(K)=\inter
{p,q\in K} E(p,q)\;\inte\;\inter
{{p\in K}\atop{q\in P-K}} C(p, q).\eqno(\Eq2)$$}

The set
$$E(K)=\inter
{p,q\in K} E(p,q)\eqno(\Eq3)$$
that constitutes the first half of equation (\Eq2) is called the {\it generalized bisector} of the set $K$: a point of $\Sscr$ is in $E(K)$ if and only if it is equidistant from all sites in $K$. Since $E(K)$ is the intersection of subspaces, it is itself an affine subspace of $\Sscr$. \note{examples?}

\footprob{\Prob{\Sbsec{\Sec6.1}.6}}{(a) Characterize the metrics of $\Sscr=\reals^k$ for which $V
P(K)$ is always convex. (b) Same for star-shapedness.}

% Miscellaneous junk from other Voronoi chapter

% additional macros

\footprob{\Prob{\Sbsec{\Sec6.1}.8}}{Prove that the Delaunay diagram (where $D(K)=\hull(K)$ if $V(K)\neq\empty$) in a Cartesian space is always the dual of the Voronoi diagram, even if the metric is not Euclidean, or give a counterexample.}

A useful intuition about the $\incircle$ test comes from the following observation. Given two points in the plane $X$ and $Y$, the set of circles passing through $X$ and $Y$ forms a one parameter family. For example, we can think of these circles as the family $\left\{C
t\right\}$, where $t$ denotes the signed distance of the center of such a circle along the bisector of $XY$, measured from the midpoint of $XY$. Thus $C
{-}$ denotes the circle corresponding to the half-plane to the left of the line $XY$, $C
0$ denoted the circle with diameter $XY$, and $C
$ denotes the circle corresponding to right half-plane of $XY$. Note that the portion of these circles to the left of $XY$ strictly decreases (by proper inclusion) as $t$ increases, while the portion to the right of $XY$ strictly increases. See fig. 8.3. The next lemma uses this intuition to derive another property of the Delaunay triangulation that will be useful to us in the next section.

\lemma{8.3}{Let $A$ be a site and consider any line $l$ through $A$. For convenience of terminology, assume that $l$ is horizontal. Let $N
1, N
2, \ldotss, N
k$ denote the Delaunay neighbors of $A$ lying above $l$, listed in counterclockwise order. If $X$ is any point of $l$ to the right of $A$, let $\Gamma
i$ denote the portion of the circumcircle of $AXN
i$ that is above $l$. Then the sequence $\left\{\Gamma
i\right\}$ is unimodal, in the sense that there is some $j$, $1jk$, such that for $1i<j$ we have $\Gamma
i\supset\Gamma
{i+1}$, while for $ji<k$ we have $\Gamma
i\subset\Gamma
{i+1}$.}

\proof{We first show that if $X
i$ denotes the rightmost intersection of the circumcircle of triangle $AN
iN
{i+1}$, $i = 1, 2, \ldotss, k-1$, with $l$, then the sequence of points $\left\{X
i\right\}$ moves monotonically to the left.

Consider, as in fig. 8.4, three consecutive Delaunay neighbors $N
i$, $N
{i+1}$, and $N
{i+2}$ of $A$. The point $N
{i+2}$ is outside the circle $AN
iN
{i+1}$ and points $N
i$ and $N
{i+2}$ are on opposite sides of $AN
{i+1}$. So to get to the circle $AN
{i+1}N
{i+2}$ from $AN
iN
{i+1}$, while always passing through $A$ and $N
{i+1}$, we must expand on the side of $N
{i+2}$, and therefore we must contract on the side of $N
i$, where $X
i$ and $X
{i+1}$ also lie. This proves our assertion.

To prove the lemma now, note that as long as the $X
i$ are to the right of $X$, then $X$ is inside the circumcircle of $AN
iN
{i+1}$, or equivalently, $N
{i+1}$ is inside the circumcircle of $AN
iX$. After the $X
i$ move to the left of $X$, then $N
{i+1}$ is outside the circumcircle of $AN
iX$. Thus the $\Gamma
i$ behave as stated.}

We will refer to lemma 8.3 as the {\it unimodality lemma}. Another useful property of the Delaunay triangulation that can be derived with the help of the $\incircle$ test is:

\lemma{8.4}{Let $A$ be a site and let $X$ and $Y$ denote any two distinct Delaunay neighbors of $A$. Then all other Delaunay neighbors of $A$ that lie inside the convex angle $\angle XAY$ are inside the circumcircle of triangle $AXY$, and all neighbors lying outside the angle are outside that same circle.}

\proof{Without loss of generality let us assume that in the convex angle $\angle XAY$ the ray $AY$ is counterclockwise of $AX$. Suppose the lemma is false inside the convex angle $\angle XAY$. Let $N$ be the Delaunay neighbor of $A$ outside the circle $AXY$ which is the first to be encounterd as we sweep this angle in counterclockwise fashion. Let also $M$ denote the predecessor of $N$, as in fig. 8.5. Note that $N$ is also outside the circle $AMY$ since $X$, $M$, and $N$ are all on the same side of $AY$. Therefore $Y$ is inside the circle $AMN$, contradicting Delaunayhood. A similar argument proves the lemma outside $\angle XAY$.}

\note{elaborate on this, and prove it. Perhaps later on. Discuss minimal triangulations, and repeated-swap algorithms (see [Lewis and Robinson]). Perhaps use in incremental algorithm?}

A straightforward algorithm for constructing the Delaunay (and the Voronoi) diagram of a set $P$ of sites on the plane follows from this last observation. Assume for simplicity that no three sites are collinear, and no four of them lie on the same circle. Then all Delaunay faces are triangles, and any three sites determine a proper circle passing through them. we need only enumerate all triplets of sites, and for each triplet $K$ test whether any other site falls inside the circumcircle of $K$; if not, the triangle determined by $K$ is a face of the Delaunay. The handling of general sets $P$ (which may contain four or more cocircular points) requires only minor modifications to this basic scheme. we will not bother to give the details, since the $O(n^4)$ running time of this algorithm makes it quite impractical. However, the central step of this algorithm --- testing if a point is interior to the circle defined by other three --- is the core of all other algorithms we are going to see, and it is worth of more attention. This test has an equivalent interpretation that is quite surprising and gives invaluable insight about the structure of Delaunay diagrams.

To compute the edges and vertices of a Voronoi region $V
p$, we can start with $V
p\gets \Sscr$ and then perform $V
p\gets V
p\inte C(p,q)$ for all $q$ in $P-\set{p}$. After each step, $V
p$ will be essentially a convex polygon, except that some of its vertices may be at infinity. We can represent such a region by the list of its vertices, in order of polar angle around the point $p$, and use the algorithms of chapter 4 to compute each intersection.

With this data structure, each intersection can be found in $O(\log n)$ time, so in $O(n\log n)$ we can compute a single region, and $O(n^2\log n)$ the whole diagram. In the worst case, the running time may be actually $\Theta(n^2\log n)$. We clearly need better algorithms.

We can use the basic data structure described in section 5.???D. However, the special nature of the Voronoi diagram allows us to introduce some simplifying modifications. First, notice that all internal angles are less than $\pi$, so (as discussed in section 5.???D) we can compute the vertices by the intersection of two adjacent edges, and don't have to store their coordinates in the structure. Furthermore, the supporting line of each edge is the bisector of the data points corresponding to the adjacent faces; if we store the coordinates of each data point in its corresponding face node, we don't need extra fields in the edge nodes for their parameters.

\note{Conjecture: randomized naive insertion is $O(n\log n)$ average.}

\note{Bucket techniques.}

\lemma{8.?}{Let $V=\set{v
0, v
1, \ldots, v
k}$ be a $k$-simplex with positive orientation, and let $S$ be its circumscribed $k$-sphere. Let $\lambda$ be the mapping from $\reals^k$ to $\reals^{k+1}$ defined by $\lambda((x
1, x
2, \ldots, x
k))=(x
1, x
2, \ldots, x
k, \sum
j x
j^2)$. Then a point $w\in \reals^k$ is on the boundary of $S$ if and only if the $(k+1)$-simplex $\set{\lambda(v
0), \lambda(v
1), \ldots, \lambda(v
k), \lambda(w)}$ is negatively oriented.}

Another application of the Voronoi diagram is in finding the largest circle $C$ devoid of $P$. If no constraints are imposed on $C$, the problem has no solution: we can always place a circle of arbitrary radius far enough from $P$ so that it includes no points of $P$. If the center of $C$ is required to lie in the covex hull of $P$, the problem becomes meaningful; using theorem 8.???, we can easily prove that the center of $C$ is either a Voronoi vertex interior to the hull of $P$, or the intersection of a Voronoi edge with an edge of the hull. It turns out that all those points, and therefore the largest $C$, can be found in $O(n)$ time \note{I guess...}.

\note{Closest $R$-$S$ pair}

\note{MST}

\note{min matching}

\note{TSP}

\note{Top of Delaunay polytope.}

An alternative that should be considered is the ``bucket'' algorithm (8.???), which is simpler, works for spaces of any dimension $k$, and is quite efficient on the average: it takes only $O(kn)$ preprocessing time, plus $O(2^k)$ time per query. Unfortunately, to derive these bounds we have to make some strong assumptions on the the probability distribution of $P$, and these assumptions hold only in very few cases. In the worst case, algorithm 8.??? performs no better than the trivial exhaustive search.

\footprob{\Prob{\Sec8.1}}{Study the ``Delaunay walking'' post-office algorithm of A. Bowyer. Can we construct a hierarchical tower of Delaunays (each level containing a subset of the sites on the one below) with $O(\log n)$ levels, so that we can locate a query in a layer by locating it on the layer above and taking at most one further step? Is this equivalent to Kirkpatrick-like point location in the Voronoi? Is there an $O(\log n)$ query time post-office algorithm that is {\it not} equivalent to point location in the Voronoi diagram?}

\note{Historical note:} This test has been used implicitly in many Voronoi algorithms [Watson, Green+Sibson, Shamos, etc.]. The correspondence between Voronoi diagrams in $k$ dimensions and convex hulls in $k+1$ dimensions went apparently unnoticed fro along time: almost every known convex hull or Voronoi algorithm was discovered at least twice {\bf actually thrice or ``fource'', if we consider duality}. The correspondence was first made explicit by ???Brown (????), using a different mapping (central projection onto a sphere). This result was used by Klee (???) and Seidel for computing the maximum complexity of a Voronoi diagram in $k$ dimensions, but its practical significance seems to have been largely ignored. The $InCircle$ predicate and the quadratic mapping $\lambda$ were explicitly defined and studied by the authors [GuiSto], who used them in a practical version of Shamos-Green-Sibson algorithm. The practical implications of the correspondence were further explored by Seidel, ???others, and the authors.