Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
13.2
Lattices
and
Delaunay Polytopes
187
(ii)
There
are two
types
of
Delaunay polytopes
of
dimension k =
2,
namely,
the
triangle
(with
no
obtuse
angles)
002
and
the
rectangle
fh
=
,2.
(Recall
Figure
13.2.4.)
(iii)
There
are
five
types
of
Delaunay polytopes
of
dimension k =
3.
They
are
the
tetrahedron
003,
the
octahedron
fh,
the
cube
,3,
the
prism
with
triangular
base (Le.,
002
x 001)
and
the
pyramid
with
square base (Le.,
Pyr(r2)).
(See
Figure
13.2.13.)
(iv)
There
are
19
types
of
Delaunay polytopes
of
dimension k =
4.
They
are
described
in
Tables V
and
VII
from
Erdahl
and
Ryshkov [1987].
Among
them,
13
can
be
obtained
from
the
Delaunay polytopes
of
dimension
1,
2
or 3 by applying
the
direct
product,
pyramid
and
bipyramid
constructions,
as
indicated
below.
- Using
the
pyramid
construction,
we
obtain
the
pyramids
with
base
003
(this gives
004),
with
base
fh
with
base ,3,
with
base
the
triangular
prism,
and
with
base
the
squared
base pyramid.
- Using
the
bipyramid
construction,
we
obtain
the
bipyramids
with
base
fh
(this
gives
(34)
and
with
base
,3.
-
By
taking
the
direct
product
of
the
3-dimensional Delaunay
polytopes
with
001,
we
obtain
the
prisms
with
base 003,
with
base
{33,
with
base
,3
(this gives
,4),
with
base
the
triangular
prism,
and
with
base
the
squared
base
pyramid.
-
By
taking
the
direct
product
of
two 2-dimensional Delaunay polytopes,
we
obtain
002
x 002. (Indeed,
002
X,2
and,2
X,2
have already
been
mentioned.)
In
addition,
we
have
the
repartitioning
polytope
P~
2 (associated
with
the
pentagonal
facet; see Section 15.2) which is one
mor~
Delaunay
polytope
of
dimension
4;
it
is
the
polytope A
in
the
Table VI from
Erdahl
and
Ryshkov
[1987].
The
remaining
five Delaunay polytopes are those
numbered
4,
5,
6, 9
and
13
in
Table V from
Erdahl
and
Ryshkov [1987].
The
number
of
combinatorial types
of
Voronoi polytopes is also known
in
small
dimension k
~
4;
for k =
2,
this
number
is 2 (rectangles
and
hexagons
being
the
two possibilities; recall Figure 13.2.4), it
is
5 for k = 3
and
52
for k =
4.
It
is
conjectured
to
be
about
75000 for k =
5.
(See Waldschmidt, Moussa, Luck
and
Itzykson
[1992]' p.479.)
13.2.5
Additional
Notes
Lattices
and
Positive
Semidefinite
Matrices.
Let P E
PSD
n
and
(Pij
)f,j=1
be
the
corresponding positive semidefinite
matrix
(setting
Pji
=
Pij).
By
Lemma
2.4.2,
there
exist n vectors
Vb""
Vn
E
Ek
(1
~
k
~
n) such
that
Pij
=
v[
Vj
for all
i,
j = 1,
...
,n,
where k is
the
rank
of
the
system
(VI,
..
.
,v
n
)
and
of
the
matrix
(Pij
)i,j=I'
So, k = n
if
P is positive definite (i.e.,
if
P lies
in
the
interior
of
PSD
n
)
and
k < n otherwise. Set L
:=
Z(Vl,""
v
n
).
Sometimes, L is a lattice.
This
is
the
case,
in
particular,
if
p is positive definite.
There
is a many-to-one correspondence between
the
positive definite
matrices
P E
PSD
n
and
the
lattices
in
En. Indeed,
the
action
on
p
of
the
group G L( n,
Z)
of
188
Chapter
13.
Preliminaries
on
Lattices
integral
unimodular
transformations
produces
distinct
bases
of
the
same
lattice
L.
The
following was proved by Voronoi [1908, 1909] (we follow
Erdahl
and
Ryshkov
[1988] for
the
exposition):
The
action
of
GL(n,
Z)
induces
a
partition
of
the
cone
PSD
n
into
disjoint relatively
open
convex subcones, called
the
L-type
domains,
of
dimension
1,2,
...
,
Ci
l
),
and
having
the
following
properties:
(i)
On
each
of
these
subcones
the
affine
structure
of
the
L-decompositions
of
corresponding
lattices
is
constant,
i.e.,
the
lattices
corresponding
to
the
points
of
a given
subcone
are all z-equivalent.
(ii)
Subcones
of
dimension
(nil)
correspond
to
general lattices, i.e.
having
simplicial
L-decompositions.
These
L-type
domains
are
polyhedral.
(iii) A
subcone
of
dimension
less
than
(nil)
is a relatively
open
face
of
two
or
more
L-type
domains.
If
such
a cone makes
contact
with
the
boundary
of
an
L-type
domain,
then
it is necessarily a face
of
that
domain.
The
lattice
corresponding
to
a
quadratic
form
on
such
a face is special, i.e.,
it
has
among
its
Delaunay
polytopes
some
that
are
not
simplices.
Voronoi [1908, 1909] showed
that,
in
any given
dimension
k,
the
number
of
distinct
(up
to
z-equivalence)
k-dimensionallattices
is finite. Therefore,
many
of
the
L-type
domains
correspond
to
z-equivalent lattices.
Delaunay
Polytopes
and
Empty
Ellipsoids.
As we will see in Section 14.1,
the
study
of
the
hypermetric
spaces
on
n
points
amounts
to
the
study
of
the
Delaunay
polytopes
of
dimension
k
::;
n - 1.
It
is also closely
related
to
that
of
empty
ellipsoids.
Indeed,
empty
ellipsoids, which arise as
the
solution sets
of
the
quadratic
functions
that
are
nonnegative
on
integer
variables,
are
nothing
but
affine images
of
empty
spheres
in
lattices.
There
is a sequence
of
papers
by
Erdahl
[1974, 1987, 1992]
and
by
Erdahl
and
Ryshkov
[1987, 1988]
studying
the
set
of
integer solutions
of
equations
of
the
form:
(13.2.14)
f(x)
:=
ao
+ L
aixi
+ L aijXiXj = 0,
l:Si,j:Sn
where
ao,
al,
...
, an E
lffi.,
aij =
aji
E
lffi.,
and
f satisfies
the
condition:
(13.2.15)
f(x)
~
0 for all x E
zn.
The
set
of
integer
solutions
of
f(x)
= 0 is called
the
root figure
of
f
and
is
denoted
by
Rf.
From
relation
(13.2.15),
the
matrix
Af
:=
(aij)lSi,jSn
is positive semidefinite
and
the
region
{x
E
lffi.n
I
f(x)
<
O}
is free
of
integral
points.
Set
E
f
:=
{x
E
lffi.n
I
f(x)
= o}.
Suppose
first
that
Af
is
positive definite.
Then,
the
set
E
f
is
an
ellipsoid
whose
interior
is free
of
integral
points;
the
ellipsoid E f is
said
to
be
empty
in
zn.
Hence,
the
root
figure R
f
consists
of
the
integral
points
lying
on
E
f
and,
thus,
is finite.
In
fact,
the
root
figure
Rf
is affinely equivalent
to
the
set
of
vertices V
of
a
Delaunay
polytope,
with
dim(V)
=
dim(Rf)
::;
n. Moreover, every finite
root
figure arises
in
this
way. (See
Erdahl
[1992].)
13.3 Finit.eness of the Number of Types of Delaunay Polytopes 189
Suppose
now
that
Af
has a nonzero kernel
4
V.
Erdahl
[1992]
shows
that
V contains
a basis composed only
of
integral vectors.
Then,
the
set contains infinite directions,
as
f(x
+ v)
f(x)
holds for all x E
lIRn,
v E V.
If
W
is
a subspace complement
of
V
in
lIR
n
,
then
Ef
'"
V +
E'
where
E'
:=
Ef
n W is an ellipsoid in W. Hence, E
f
can
be
seen as a "cylinder" with axis
V and ellipsoidal section;
we
say
that
is a degenerate
ellipsoid with axis
V.
In this case,
the
root figure
Rf
is
also infinite.
Tn
fact, every
infinite
root
figure arises from
the
finite ones
by
a simple construction; essentially, every
infinite
root
figure is
of
the
form
R+
r where R
is
a finite root figure
and
r
is
a
sublattice
of
zn
(see
Theorem
2.1 in
Erdahl
[1992]).
Therefore,
the
study
of
the
root figures
amounts
to
the
classification
of
the
Delaunay
polytopes
of
dimension k
::s
n.
Finally, consider
the
cone:
Q+(zn):",
{a'"
(ao,a!,
...
ao
+
2:.::
alxi
+
19:O;n
l$i$j$n)1
aijXiXj
2::
0 for all x E
zn},
i.e., each
member
a E
Q+(zn)
corresponds
to
a function
fa
satisfying (13.2.14)
and
(13.2.15).
Erdahl
[1992]
shows
that
every a E lying
on
an
extreme
ray
of
Q+(zn)
satisfies one
of
the
following:
(i)
fa
is
constant
(i.e.,
al
an aij 0),
(ii) fa(x) =
CCl:O;i:::;n
aiXi
+
'1])2
where
(al,'"
,an)
is
not proportional
to
an
integer
vector,
(iii)
fa is perfect which, in
the
terminology
of
Erdahl
[1992]' means
that
the
dimension
of
the
set
{b
E
Q+(zn)
I
Rf.
~
Rib}
is
equal
to
1.
Clearly,
the
hypermetric cone
HYP
n
+
1
is (via
the
covariance mapping) a section
of
the
cone
Q+(zn),
as
~(HYPn+1)
{a
Q+(zn)
lao'"
0 and ai
'"
-aii
for i
'"
1,
...
,n}.
Note
that
the
notion
of
root figure corresponds
to
that
of
annullator, used in Sections 14.2
and
15.1. Moreover, there is
the
following link between
the
perfect elements
of
Q+(zn)
and
the
extreme
rays
of
HYP
n+
1:
For d E
HYP
n+
1,
d lies on
an
extreme ray
of
HYP
n+
1
if
and
only if
~(d)
is a perfect element
of
Q+(zn).
13.3
Finiteness
of
the
Number
of
Types
of
Delaunay
Polytopes
Recall
that
two lattices
£,
L'
are z-equivalent
if
there exists
an
affine bijection T
such
that
£'
T(£)
and
T brings
the
star
of £ on
the
star
of
£'.
(Note
that
any
k-dimensional lattice is
afJinely equivalent
to
Zk!) Voronoi [1908, 1909] proved
that
the
number
of
distinct,
up
to
z-equivalence, k-dimensionallattices is finite.
This
implies obviously
that
the
number
of distinct, up
to
affine equivalence, k-
dimensional Delaunay polytopes
is
finite.
In
other
words,
the
number
of
types of
k-dimensional Delaunay polytopes is finite. (Recall
that
two Delaunay polytopes
have
the
same
type
if they are affinely equivalent.)
kernel of a
matrix
A is
the
set
Ker
A consisting
of
all
vectors x
such
that
Ax
O.
190
Chapter
13. Preliminaries
on
Lattices
We give here a direct
proof
of
the
finiteness of
the
number
of
types
of
Delau-
nay
polytopes
in
Rk
since Voronoi's original
proof
is
very involved; it is
taken
from Deza,
Grishukhin
and
Laurent
[1993].
Let 1
be
a
type
of
Delaunay polytopes
of
dimension
k.
A subset B
t:::;
Rk
is
called a
representative basis
of
1 if
there
exist a Delaunay
polytope
P
of
type
1
and
a
lattice
L
t:::;
Rk
which contains
the
set
V(P)
of vertices
of
P
and
admits
B
as a basis. (Note
that
L
may
be
larger
than
the
lattice
L(P)
generated by
the
set
of
vertices
of
P.)
Suppose
that
P
has
N vertices
and
let
Qp
denote
the
N x k
matrix
whose
rows are
the
vectors v E
V(P).
Let
MB
denote
the
k x k
matrix
whose rows are
the
members
of
B.
Then,
there
exists
an
integer N x k
matrix
Y'Y
such
that
(13.3.1)
If
pI
is
another
Delaunay
polytope
of
type
I,
i.e., if
pI
=
T(P)
for some affine
bijection
T,
then
the
relation
holds. Hence,
the
matrix
Y'Y
characterizes
the
type
1 (once a representative basis
B
has
been
chosen).
The
next result shows
that,
for each
type
I,
one
can
choose
a representative basis
B in such a way
that
the
matrix
Y'Y
has
a very special
form, which will
imply
that
there
are only finitely
many
possibilities for Y
r
Proposition
13.3.2.
Let
1
be
a type
of
Delaunay polytopes
of
dimension
k.
One can choose a representative basis B
of
1
in
such a way that the
matrix
Y'Y
satisfies the following relations:
(i) There exists a k x k
submatrix
D =
(aijh$i,j9
of
Y'Y
which is lower
triangular and satisfies:
0
:S
aij
<
aii
for
aliI
:S
j < i
:S
k.
(ii) p = I det(D)1 is the
maximum
possible value
of
the absolute value
of
the
determinant
of
any
k x k
submatrix
of
Y'Y.
(iii) p
:S
k!.
For
the
proof,
we
need
the
following classical result
about
lattices from Cas-
sels
[1959].
Proposition
13.3.3.
Let
L,
L'
be
two
k-dimensional
lattices
in
Rk
such that
L'
t:::;
L.
For every basis
{al,
...
,ad
of
L',
there exists a basis
{b
1
,
...
,bd
of
L
such
that
for
i = 1,
...
,k,
where
(aij)l$i,j$k
are integers satisfying
13.3
Finiteness
of
the
Number
of
Types
of
Delaunay
Polytopes
191
for
all 1
::::;
j < i
::::;
k.
I
Proof
of
Proposition
13.3.2.
Let
P
be
a
Delaunay
polytope
of
type
I
with
N
vertices
and
let
L
be
a
lattice
in
~k
containing
the
set
of
vertices
V(P)
of
P.
Let
Vo
be
a
subset
of
V(P)
of
size k
and
let
Qo
denote
the
k x k
submatrix
of
Qp
whose rows
are
the
members
of
Vo.
We choose
Vo
in
such
a way
that
I det(Qo)1
is
largest
possible. We
can
suppose
that
Qo
is
the
submatrix
of
Qp
formed by
its
first k rows.
The
lattice
L'
:=
Z(Vo) is a
sublattice
of
L
and
admits
Vo
as a
basis.
Applying
Proposition
13.3.3, we
deduce
the
existence
of
a basis B
of
L
such
that
Qo
=DMB,
where
D is a lower
triangular
integer
matrix
satisfying
Proposition
13.3.3 (ii).
Let
us
choose B as
representative
basis for
the
type,.
Then,
as
Qp
=
(QpMi/)MB,
by
comparing
with
relation
(13.3.1), we
obtain
that
Qp(MB)-l
coincides
with
the
integer
matrix
Y1"
Note
that
the
matrix
Qp(MB)-l
is
an
N x k
matrix
whose first k rows form
the
matrix
D
with
= Idet(D)1 = Idet(Qo)1 =
Idet(Qo)l.
p I
det(MB)1
det(L)
Hence,
by
the
choice
of
Qo,
the
absolute
value
of
the
determinant
of
any k x k
submatrix
of
Y1'
=
Qp(MB)-l
is less
than
or
equal
to
p. Therefore,
Y1'
satisfies
the
conditions
(i),(ii)
of
Proposition
13.3.2.
Finally,
we
check (iii).
Let
Do
denote
the
simplex
whose vertices
are
the
members
of
Vo,
i.e.,
the
rows
of
Qo.
Then,
Do
is
contained
in
P
and,
thus,
vol(Do)
::::;
vol(P).
But,
vol(Do)
= I
det~~o)1
= p
d~~(L)
and
vol(P)::::;
det(L)
from
Proposition
13.2.10.
This
implies
that
p
::::;
k!.
I
We
can
now show
the
finiteness
of
the
number
of
types
of
Delaunay
polytopes
in
~k.
Theorem
13.3.4.
The
number
of
types
of
Delaunay
polytopes
in
~k
is finite.
Proof.
Every
type
I
of
Delaunay
polytopes
in
~k
with
N vertices
is
characterized
by
an
N x k
integer
matrix
Y1'
satisfying
Proposition
13.3.2 (i)-(iii).
It
suffices
to
show
that
there
is only a finite
number
of
such
matrices.
For
this,
we show
that,
for fixed p,
there
is
only a finite
number
of
matrices
satisfying
Proposition
13.3.2 (i)-(ii).
Let
Y
be
an
N x k integer
matrix
satisfying
Proposition
13.3.2 (i),(ii).
Sup-
pose
that
D
is
the
upper
k x k
submatrix
of
Y.
Then,
the
upper
k x k
submatrix
of
Y
D-
i
is
the
identity
matrix.
Let
rih
be
a nonzero
entry
of
Y
D-
1
,
where
k + 1::::;
::::;
Nand
1
::::;
h
::::;
k.
Let
C
denote
the
matrix
obtained
from
192
Chapter
13.
Preliminaries
on
Lattices
D by
replacing
its
h-th
row by
the
i-th
row
of
Y.
By
Proposition
13.3.2 (ii),
I det(C)I-::::
p.
On
the
other
hand,
I
det(CD-1)1
=
ITihl,
implying
that
ITihl
= Idet(C)1 E
{o,~,
...
,P-1,1}.
p p p
Since Y
D-
1
is
an
N x k
matrix
with
N
-::::
2k
(from
Proposition
13.2.8),
we
deduce
that,
for fixed p
and
k,
there
is only a finite
number
of
such
matrices
Y
D-
1
.
Now, D is a k x k integer
matrix
with
p = 0011
..
.
akk
and
satisfying
Proposition
13.3.2 (i); therefore,
there
is only a finite
number
of
such
matrices
D.
Consequently,
there
is a finite
number
of
possibilities for
Y.
I
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_14, © Springer-Verlag Berlin Heidelberg 2010
Chapter
14.
Hypermetrics
and
Delaunay
Polytopes
In
this
chapter
we
establish
the
fundamental connection existing between hyper-
metric
spaces
and
Delaunay polytopes. Hence, for a hypermetric distance space
(X,
d), one may
speak
of
its associated Delaunay polytope P
d
;
the
case when
(X,
d)
is
el-embeddable
corresponding to
the
case when P
d
can
be
embedded
in
a parallepiped. As
an
application of this connection, one
can
show polyhedrality
of
the
hypermetric
cone; several proofs for this fact are given in Section 14.2. As
another
application
(and
using
the
classification
of
the
irreducible root lattices),
one
can
characterize
the
graphs whose shortest
path
metric
is
hypermetric or e
1-
embeddable. Such graphs arise essentially from cocktail-party graphs, half-cube
graphs,
and
a single
graph
on 56 nodes
(the
Gosset graph) by taking
Cartesian
products
and
isometric subgraphs (see Section 14.3). We group in Section 14.4
several results concerning spherical representations
of
distance spaces
and
the
radius
of
Delaunay polytopes.
14.1
Connection
between
Hypermetrics
and
Delaunay
Polytopes
In
this section,
we
establish
the
fundamental connection existing between hy-
permetric
spaces
and
Delaunay polytopes.
This
connection was discovered by
Assouad [1982, 1984]; it
is
stated
in
Theorem
14.1.3, whose
proof
is based on
the
next
two propositions.
Proposition
14.1.1.
Let c,
Vo
:=
0,
VI,
...
,V
n
E
IRk
be
vectors satisfying
(i)
II
Vi
- c
11=11
c
II
for 1
:::::
i
:::::
n,
(ii)
II
2:1<i<n
biVi
- c
II~II
c
II
for all b E
zn.
Then, the set L
:=
Z(V1," .
,v
n
)
is a lattice.
Proof.
For b E
zn,
set v(b)
:=
2:1::;i::;n
biVi;
then, v(b) ±
Vi
E L. Hence, (ii) yields
(Vi
± v(b) - c)2
~
c
2
, i.e.,
(Vi
- c)2 +
(V(b))2
±
2(Vi
-
cf
v(b)
~
c
2
which, together
with
(i), implies
(a)
(V(b))2
~
21(vi
- c)T
v(b)1
for 1
:::::
i
:::::
n.
194
Chapter
14.
Hypermetrics
and
Delaunay
Polytopes
Consider
the
units
vectors
V·
- c v(b)
ei:=
W for i =
0,1,
...
,n,
and
e(b):=~.
Set
(3:=
min{max(e[
U
11
::;
i
::;
n)
I U E
l~\
II
U
11=
1}.
We show
that
(3
>
O.
Then,
(a) will
imply
that
II
v(b)
112:
2(3
II
c
II
for all
b E
zn
such
that
v(b)
i=
OJ
in
other
words,
the
open
ball
centered
at
the
origin
with
radius
2(3
II
c
II
contains no
other
lattice
point
besides
the
origin, which
shows
that
L is a lattice. Suppose
that
(3
=
O.
Then,
we
can
find a sequence
(Up)P?1
of
unit
vectors
of
~k
such
that
Ie;
upl
::;
~
for
any
1
::;
i
::;
n,
P
2:
1.
By
the
compactness
of
the
unit
sphere,
we
can
suppose
that
the
sequence
(Up)p?l
admits
a
limit
U
when
P goes
to
infinity (replacing,
if
necessary,
(Up)p?l
by
a
subsequence). Therefore,
II
U
11=
1,
while
e;
U = 0 for i =
1,
...
,n,
implying
that
U = 0 since
the
vectors
VI,
...
,V
n
span
~k.
We have a
contradiction.
This
shows
that
(3
>
O.
I
Proposition
14.1.2.
Let
(X,
d)
be
a distance space, X =
{O,
1,
...
,n}.
The
following assertions
are
equivalent.
(i)
(X,
d)
is hypermetric.
(ii)
(X,
d)
has a representation i E X
f-+
Vi
E
~k
{where k
::;
n}
on a sphere S
which is empty in the set
Laj(X,
d)
:=
{L
biVi
I
bE
ZX
and L b
i
= 1}.
iEX iEX
Proof. (i)
==}
(ii) Since (X,
d)
is
of
negative
type,
we
know from Proposi-
tion
13.1.2
that
(X,
d)
has a
representation
vo,
VI,
...
,V
n
E
~k
for some 1
::;
k
::;
n. Moreover,
the
system
(vo,
...
, v
n
)
has
rank
k
and
we
can
suppose
without
loss
of
generality
that
Vo
=
O.
We first show
that
the
vectors
Vo,
VI,
...
,V
n
lie
on
a sphere, i.e.,
that
there
exists c E
~k
such
that
(a)
2c
T
Vi
=
V;
for 1
::;
i
::;
n.
If
k =
n,
then
the
vectors
VI,
...
,
Vn
are
linearly
independent
and,
therefore,
the
system
(a)
admits
a
unique
solution
c.
Suppose
that
k
::;
n -
1.
Let M
denote
the
n x k
matrix
whose rows
are
the
vectors
VI,
...
,V
n
,
let U
denote
the
subspace
of
~n
spanned
by
the
columns of M
and
set f
:=
(vi, ... ,v;)T.
The
system
(a)
has
a
solution
if
and
only
if
fEU
or, equivalently,
if
fT
9 = 0 for each 9 E
U.L
(U.L
is
the
orthogonal
complement
of U
in
~k).
Take 9 E
U.L,
let
bE
zn
such
that
Igi
- b
i
I < 1 for i =
1,
...
,n
and
set {j
:=
9 -
bj
so {j belongs
to
the
unit
cube. Set
p:=
~(d).
Then,
Pij
=
v;
Vj
for 1::; i < j
::;
n. Using
relation
(13.1.4),
we
deduce
that
L bibjPij - L
biPii
2:
0, i.e.,
I~i,j~n
I~i~n
14.1
The
Connection between Hypermetrics
and
Delaunay Polytopes
195
(b)
Therefore,
Fb=
L
biv;S(
L
biVi)2
(b™)2
(g™
oTM)2=(OTM)2,
l:'Oi:'On
19:'On
since g E
U1-.
Hence,
Fb
S (oTM)2, implying
that
Fg
S
Fo
+ (oTM)2. This
implies
that
fT
g =
0;
otherwise, the left hand side of the
latter
inequality could
be
made
arbitrarily large while its right hand side
is
bounded. Note
that
the
solution c to
the
system (a) is unique since (VI,'
..
,v
n
)
has full rank
k.
From (a)
and
(b),
we
deduce
that
for all b E ZX with
b;
1. This shows
that
the sphere S with center c
and
radius
II
c
II
is empty
La/(X,
d).
(ii)
===?
(i) Let
bE
ZX with
bi
1.
Then,
L
bibjd(i,j)
;,jEX
L bibj(Vi
i,jEX
C + c Vj)2 = L bibj(2r2 -
2(Vi
-
cf(vj
- c))
i,jEX
2(L
bi(Vi - c))2 = 2(r2 -
(L
biVi
- c)2) S 0
iEX
iEX
since the sphere S is
empty
in
La/(X,
d). This shows
that
(X,
d)
is hypermetric.
I
As
a consequence
of
Propositions 14.1.1
and
14.1.2,
we
have
the
next theorem
which summarizes the connection existing between hypermetrics
and
Delaunay
polytopes.
Theorem
14.1.3. Let
(X,d)
be
a hypermetric space,
IXI
=
n+1.
There exist a
k-dimensional Delaunay polytope
Pd
in Rk, for some 1 S k S
n,
and a mapping
which is generating, which means that the set
{Vi
liE
X}
generates the
set
of
vertices V(Pd)
of
Pd,
and such that
d(i,j)
=
(v;
- Vj)2 for
i,j
EX.
Moreover, the pair (Pd, fd) is unique, up to translation and orthogonal transfor-
mation.
I
196
Chapter
14.
Hypermetrics and Delaunay Polytopes
We
refer to
Pd
as
the
Delaunay
polytope associated with the
hypermetric
space
(X,
d),
the
lattice
bvv I
bE
ZV(P
d
)
and
L b
v
=
I}
vEV(P
d
)
is denoted as
Ld
and
the
sphere circumscribing
Pd
as Sd.
As another application of Propositions 14.1.1
and
14.1.2,
we
obtain the
fol-
lowing charact,erization for Delaunay polytopes.
Proposition
14.1.4.
Let
P
be
a polytope
of
dimension
k
in
Rk.
Then,
P is a
Delaunay
polytope
if
and
only
if
the following assertions hold,
(i)
The
distance space
(V(P),
d(2)) is hypermetric.
(ii)
If
Q is a polytope
of
dimension
k
in
Rk
such
that
(iia)
V(P)
<;:;
V(Q),
(iib)
Zaj(V(P))
=
Zaj(V(Q)),
and
(iic) the distance space CV(Q),d(2)) is hypermetric,
then
P
and
Q coincide.
I
For instance, take for Q a square (2-dimensional hypercube) and for P
the
triangle having as vertices three
of
the vertices of Q. Then, P satisfies (i),
but
not
(ii). Indeed,
the
triangle P is
not
a Delaunay polytope as
it
ha..'i
a right
angle. Recall
that
a triangle is a Delaunay polytope if
and
only if
it
has no
obtuse angle.
On
the
other
hand, there exist pairs of Delaunay polytopes
(P,
Q)
of the same dimension in
Rk
and
satisfying (iia), (iic),
but
not (iib). Such
an
example is given in Section 16.4
for
the Barnes-Wall lattice (see the pair
(Q,
P)
there).
Note
that
we
may
a..'lsume
to be dealing with hypermetric distances taking
nonzero distances between distinct points (i.e., with metrics). Indeed, let
(X,
d)
be
a space with
d(io,jo)
= 0 for two distinct points
io,jo
E
X,
and
let
(X'
X \
{jo},d)
denote
its
subspace on X \
Uo}.
Then,
both
(X,d)
and
(X',
d)
have the same associated Delaunay polytope P (simply representing jo
by
the
same vertex
of
P as i
o
).
We
would like to emphasize the following fact, since it will be often used in
the
sequel.
Proposition
14.1.5.
Let
(X,
d)
be
a
hypermetric
space with representation
(Vi
liE
X)
in
the
set
of
vertices
of
its associated
Delaunay
polytope Pd. Given
bE
ZX
with
b;
1,
L
b;bjd(i,j)
i,jEX
o
~
L
biVi
is a
vertex
of
Pd·
iEX