From pjyamamo Wed Aug 18 13:29:40 1993 remote from watdragon
Subject: Re: RGI lecture notes: Edelsbrunner
Date: Wed, 18 Aug 1993 13:29:40 -0400 (EDT)

Poster's comment:

These notes were prepared using LaTeX.
Most of the syntax is self-explanatory and similar to other type-setting styles.
\keyword: \ indicates a keyword follows.
$ expression $: $'s denote a mathematical expression.
$ _ $: _ represents a subscript
$ ^ $: _ represents a superscript
\ldots: represents "..."
{ group }: {} denote a grouping of an expression.

------------------------------------------------------------------------------

\documentstyle[11pt]{article}
\begin{document}
\title{Delaunay and regular triangulations in space}
\author{Prof. Herbert Edelsbrunner.}
\date{July 26, 1993}
\maketitle
\footnote{ Scribes : Pedro Ramos, Saugata Basu}
This talk was mostly devoted to definitions of Voronoi cells,
nerves, simplicial complexes, Delaunay triangulations, circular
inversions  ,stereographic projections, and their 
applications to computational geometry.

The following open problem was posed at the beginning of the talk.

Suppose there are $2n$ unit disks, $A_1, A_2,\ldots , A_n, B_1,
B_2,\ldots ,B_n $, with centers at $a_1, a_2, \ldots ,a_n, b_1,
b_2,\ldots ,b_n$  such that,

\[  |a_i - a_j|  \geq |b_i - b_j| \;\; \forall i,j \]
then does it follow that,

$ AREA (\cup_i A_i)   \geq AREA (\cup_i B_i) $ ?  
This problem was first posed by Poulsen (1954) and Kneser (1955).

An approach that one might take to prove this is to use inclusion-exclusion.
Indeed, if the disks come closer together the area of their pairwise
intersections increase, and since these get subtracted the inequality
works in the right direction. However, we then have the case of intersections
of every triples and now the inequality is in the opposite direction
to what we desire in the proof. 

Another approach to this problem is to look at the decomposition of
the union of the disks, by the Voronoi diagram induced by the centers
of the disks.

First, we need some definitions.

{\bf Def.} Given a collection of sets $\cal{A}$, the nerve of $\cal{A}$ 
(denoted by $N(\cal{A})$) is defined to be 
$N(\cal{A}) = \{ X \subseteq \cal{A} | \cap_{A_i \in X} A_i \neq \emptyset \}$ .

{\bf Def.}  A collection $\cal{K}$ of sets is an abstract
simplicial  complex if  $\sigma \in \cal{K}$ and $\tau \subset \sigma$
implies $\tau \in \cal{K} $.

Given a set of points in the plane, we can define the $\cal{A}$ to be
the collection of the Voronoi cells. The nerve of $\cal{A}$, then
consists of singletons, pairs, and triples of these cells. 
If we join pairs of points, whose corresponding pair of 
Voronoi cells occur in the nerve, by line segments we get the dual of the
Voronoi diagram, also called the Delaunay triangulation. The 
triangles in the Delaunay triangulation, corresponds to the
triples of Voronoi cells occurring in the  nerve. Thus the 
Delaunay triangulation corresponds to a geometric realization of
the nerve. The geometric realization in this case is the collection
of various dimensional simplices whose vertices occur as sets in the nerve.

We can also give another definition of the Delaunay triangulation
which depend only on the local properties of the points. A simplex
is in the Delaunay triangulation if and only if the interior of
the $d$-sphere passing through the $(d+1)$ vertices of the simplex
does not contain any of the other points.

{\bf Def.} A collection $\cal{K}$ of simplices is a simplicial
complex if 

i)$ \sigma \in \cal{K} $ and $\tau$ is a face of $\sigma$  imply that $
\tau \in \cal{K}$ and,

ii) $\sigma_1, \sigma_2 \in \cal{K}$ , implies that $ \sigma_1 \cap \sigma_2 =
\emptyset$ , or $\sigma_1 \cap \sigma_2$ is a face of both $\sigma_1$
and $\sigma_2$.


{\bf Def.} A $k$-simplex in $R^d$ , $0 \leq k \leq d$, is the
convex hull of $k+1$ affinely independent points in $R^d$.

Note that, any subset of $l+1 \leq k+1$  points of a simplex define
an $l$-simplex which is called an $l$-face of the $k$-simplex.

We can observe that in the plane, any triangulation of a polygon has
the same number of triangles. The situation is not the same in other
dimensions. As an example, consider the octahedron in dimension three:
if we have a regular octahedron, it can be decomposed in four
tetrahedra, but if we twist the vertices in such a way that two of
de diagonals do not cut each other, then we obtain five tetrahedra.
Question: what happens if we twist the tetrahedron in such a way that 
the three diagonals do not cross each other?

We next give the definition of an important transformation.

{\bf Def.} The inversion with center $z$ is a map,
\[ ^o: R^d-\{z\} \rightarrow R^d-\{z\}  \]
\[   x \rightarrow x^o = \frac{x}{|x|^2}  \]

The following properties of the inversion map are easy to prove.

i) $(x^o)^o=x$

ii) If $S$ is a sphere such that $ z\not \in S$ then $S^o$ is a
sphere.

iii) If $z\in S$ then $S^o$ is a hyperplane.

{\bf Def.}
Let $\pi$ be a d-sphere and let $z\in \pi$. The stereographic
projection is the map from $\pi$ to $\pi^o$ that sends the point $x\in
\pi$   to $x^o$.

Claim: 
If $S$ is a  $(d-1)$-sphere in $\pi$ then $S^o$ is a $(d-1)$-sphere in
$\pi^o$ (or a $(d-1)$-plane if $z \in S$).

Proof: 
Let $S_1$ the sphere passing through $S^o$ and $z$ and let $S_1^o$ its
inversion.
Then $S_1^o$ is a plane which cuts $\pi$ in $S$. This proves the
claim.

Let $S$ be a set of points in $R^d$ and let $S^o$ be its image via
inversion. If $P$ is the convex hull of the set $S^o$ and $\cal{K}$ is the
stereographic projection of the boundary complex of $P$ then it can be
proved that $\cal{K}$ is the Delaunay triangulation of the set $S$.

\end{document}