Introduction
171
by Assouad [1984))
that
their
Delaunay polytope spaces
are
hypermetric
and,
conversely, every hypermetric space
can
be realized as a subspace
of
a Delaunay
polytope
space (see
Theorem
14.1.3). To each hypermetric space
(X,
d) corre-
sponds
an
(essentially unique) Delaunay polytope
Pd
whose dimension
is
less
than
or
equal
to
IXI-
1.
Hence, there is a connection between
the
members of
the
hypermetric cone
HYP
n
and
the
Delaunay polytopes
of
dimension k
~
n
1.
An
interesting application
of
this connection is for proving
that
the
hyper-
metric
cone is a polyhedral cone (see
Theorem
14.2.1).
These
two objects: hypermetric cone
and
Delaunay polytopes, have been
studied
for
their
own sake. For instance,
the
hypermetric cone
HYP
n
arises
in
connection with
fl-metrics
(recall
Lemma
6.1.7);
it
forms a linear relaxation for
the
cut
cone and, as such, its facial
structure
has been intensively investigated;
results
in
this
direction will
be
given
in
Chapter
28.
On
the
other
hand,
Delaunay
polytopes
have
been
mostly
studied
in
the
literature
from
the
classical
point
of
view
of
geometry of numbers: holes, L-decomposition of
the
space,
dual
tiling
by Voronoi polytopes, etc.
The
approach taken here is
to
study
the
metric
structure
of
their
sets
of
vertices. Moreover, taking advantage
of
the
interplay
with
hypermetrics,
we
can
transport
and
exploit some
of
the
notions defined for
the
hypermetric
cone
to
Delaunay polytopes
and
vice versa.
For instance, there
is
a
natural
notion of rank for hypermetrics (namely,
the
dimension
of
the
smallest face of
the
hypermetric cone
that
contains a given
hypermetric
distance).
We
introduce
the
corresponding notion of
rank
for De-
launay
polytopes.
This
notion of
rank
permits, for instance,
to
shed a new light
on a classical
notion
studied
by Voronoi; namely,
the
repartitioning polytopes
which correspond
to
the
facets
of
the
hypermetric cone.
The
other
extreme case
for
the
rank,
namely
the
case
of
rank
1 for the extreme rays of
the
hypermetric
cone, corresponds
to
the
class
of
extreme Delaunay polytopes. A Delaunay poly-
tope
P is
extreme
if
and
only
if
the
only affine transformations T for which
T(P}
is still a Delaunay
polytope
are
the
homotheties (see Corollary 15.2.4). Several
examples
of
extreme
Delaunay polytopes
are
presented
in
Chapter
16 arising,
in
particular,
in
root
lattices or
in
sections
of
the
Leech lattice
A24
and
of
the
Barnes-Wall lattice
A16.
Historically, Delaunay polytopes
and
the
corresponding
L-partitions
of
the
space were introduced by G.F. Voronoi
at
the
beginning of
this
century.
The
so-called
empty
sphere
method
was developed
later
by
B.N. Delallnayl, who
showed
that
it yields
the
same
partition
of
the
space as Voronoi's
L-partition.
The
topic
has
been
studied
extensively
mainly
by
the
Russian school, especially
by B.N. Delaunay, E.P. Baranovskii, S.S. Ryshkov,
and
also
by
R.M.
Erdahl
from
Canada.
In
dimensions 2
and
3, L-decompositions are used
in
computa-
tional
geomet
ry
2
under
the
name
of
Delallnay triangulations; actually, nonlattice
refer
to
the
preface of
the
volume
edited
by Novikov
et
aI. [1992] for a detailed historical
account
on
the
work of B.N. Delaunay.
zFor
information
see, for
instance,
Chapter
13 in
Edelsbrunner
[1987]
or
the
survey
by