Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
14.3
Delaunay
Polytopes
in
Root Lattices
207
•
The
Delaunay
polytope
circumscribed by
the
empty
sphere
with
center C
a
and
radius
Ta
has
for vertices
the
following
Lb
(n+;-a). m vectors
(1
b,
on+1-a-b;
(_I)b,
oa-b) for 0
::;
b
::;
a,
n +
1-
a,
where
the
first b ones are chosen
among
the
n +
1-
a
positions
of
the
entries
n~l
of C
a
and
the
last b minus ones are chosen
among
the
a positions of
the
entries -
n;t~la
of
Ca.
Its
I-skeleton
graph
is
the
Johnson
graph
1
J(n
+
I,
a).
Case
of
D
n
,
n
2::
4.
• Dn =
{x
E
zn
I
L1:S;i:S;nXi
E 2Z}.
•
The
roots
of Dn
are
the
2n(n
- 1) vectors
±ei
± ej for 1
::;
i
1=
j
::;
n.
•
There
are two
types
of
empty
spheres
in
D
n
,
namely,
an
empty
sphere 8
1
with
center
C1
= (0,
...
,0,1)
and
radius
T1
=
I,
and
an
empty
sphere 8
2
with center
-
(1
1) d
d'
-
0i
C2
-
2"'"
2
an
ra
!Us
T2 - 2 •
•
The
Delaunay
polytope
circumscribed
by
the
sphere 8
1
has for vertices
the
2n
vectors (0,
...
,0),
(0,
...
,0,2)
and
(0,
...
,0,
±I,
0,
...
,0,1)
where
the
component
±I
is in one of
the
first n - 1 positions.
This
is
the
cross-polytope
(3n
whose
I-skeleton
graph
is
the
cocktail-party
graph
K
nx
2.
•
The
Delaunay
polytope
circumscribed by
the
second sphere 8
2
has
for vertices
the
2
n
-
1
vectors x E
{O,
I}n
with
L1
<i<n
Xi
E 2Z.
This
is
the
half-cube
hrn
whose I-skeleton
graph
is
the
half-cube
graph
!H(n,
2).
It
corresponds
to
a deep
hole
in
Dn.
Note
that,
for n =
4,
(34
and
hr4 are congruent (i.e., coincide
up
to
orthogonal
transformation
and
translation).
Case
of
Es.
• Es =
{x
E
~s
I x E
ZS
u
(!
+ Z)S
and
L1<i<S
Xi
E 2Z}, i.e., Es is
the
lattice
generated
by
Ds
and!
L1<i<S ei.
The
lattice
Es is even
and
unimodular;
hence,
Eg
= Es.
--
•
The
roots
of Es are
the
240
vectors
±ei
± ej
and
!(±e1
±
...
± en), where
there
is
an
even
number
of
minus signs in a root of
the
second kind.
•
There
are two
types
of
empty
spheres in E
s
,
namely,
the
sphere 8
1
with
center
C1
=
(1,0
7
)
and
radius
T1
=
I,
and
the
sphere 8
2
with
center C2 =
(~,
f)
and
radius
T2
=
/fJ.
•
The
Delaunay
polytope
circumscribed by
the
sphere 8
1
has for vertices
the
following 16 vectors
(OS),
(2,0
7
),
(1,0,
...
,0,
±I,
0,
...
,0),
where
±I
is
in
one of
the
last seven positions.
This
is
the
cross-polytope
(3s
whose I-skeleton
graph
is
K
sx2
.
It
corresponds
to
a deep hole in E
s
.
•
The
Delaunay
polytope
circumscribed by
the
sphere
82
has
for vertices
the
following 9 vectors
(OS),
(!,
...
,
!)
and
(1,0,
...
,0,
I,
0,
...
,0),
where
the
second
'For
1
:'S
t
:s;
n,
the
Johnson
gmph
J(n,
t) is defined as
the
graph
with
node
set
{A
~
{I,
...
,
n}
:
IAI
=
t}
and
with
edges
the
pairs
(A,
B)
with
IA n BI = t - 1.
208
Chapter
14.
Hypermetrics
and
Delaunay
Polytopes
1 is
in
one
of
the
last
seven positions.
This
is
the
simplex
as
with
I-skeleton
graph
Kg.
We
point
out
that,
as Es is
an
even
unimodular
lattice,
none
of
its
Delaunay
polytopes
is
generating
(by
Lemma
13.2.6).
Case
of
E
7
•
•
The
root
lattice
E7 consists
of
the
vectors
of
Es
that
are
orthogonal
to
a given
minimal
vector
Vo
of
Es.
If
we
choose
Vo
=
(~,
... ,
~),
then
E7 =
{x
E
Es
I
2::1<i<S
Xi
=
O}.
Another
choice for
Vo
could
be
Vo
=
(1,1,0
6
);
we will work
with
this-second definition
of
E7
in
Section 16.2
(in
fact,
we
shall
use
there
for E7
the
following affine
translate
{x
E
Es
I x
T
Vo
=
Xl
+
X2
=
I}).
•
There
are
two
types
of
empty
spheres
in
E
7
, namely,
the
sphere
51
with
center
C1
= (f, -!
6)
and
radius
r1
= If,
and
the
sphere
52
with
center
C2
=
(~,
-i
7)
and
radius
r2
=
j"i.
•
The
Delaunay
polytope
circumscribed
by
the
sphere
51
has
for vertices
the
56
vectors
C1
±
(~2,
_!6).
This
is
the
Gosset
polytope
3
2
1 whose
I-skeleton
graph
is
the
Gosset
graph
G
56
.
It
corresponds to a deep hole
in
E
7
•
•
The
Delaunay
polytope
circumscribed
by
the
sphere 52
has
for vertices
the
8
following vectors
(Os)
and
(1,0,
...
,0,
-1,0,
...
,0),
where
-1
is
in
one
of
the
last
seven positions.
This
is
the
7-dimensional simplex
a7
with
I-skeleton
graph
Ks.
Case
of
E
6
•
•
The
root
lattice
E6
consists
of
the
vectors
of
Es
that
are
orthogonal
to
two
nonorthogonal
given
minimal
vectors
Vo
and
wo
of
Es.
If
we choose
Vo
=
(1,1,0
6
)
and
wo
=
(_~s),
then
E6
=
{x
E
Es
I
Xl
+
X2
=
X3
+ ... +
Xs
=
O}.
(In
Section
16.2,
we
select differently
Vo
and
wo
and
we
consider
an
affine
translate
as E6.)
•
There
is
only
one
type
of
empty
sphere
in
E
6
.
Its
radius
is
Ii
and
it
cir-
cumscribes
the
Delaunay
polytope
whose vertices are
the
following 27 vectors
(
1 1
5 1
5
) ( I
1 5 1
5
)
h
5··
f
hI'
. . d
2'
-2'
6'
-6
'
-2'
2'
6'
-6
were
6 IS
III
one 0 t
east
SIX
positIOns,
an
(0,0,
-
~
2,
~
4)
where
the
two -
~'s
are
in
the
last
six positions.
This
is
the
Schliifli
polytope
221
whose
I-skeleton
graph
is
the
Schliifli
graph
G
2
7.
So
the
star
of
E6
contains
only
copies
of
221
and
of
its
image
under
central
symmetry.
We
summarize
in
Figure
14.3.1 some
information
about
the
Delaunay
poly-
topes
P arising
in
the
irreducible
root
lattices. For each
irreducible
root
lattice
L, we list all
the
Delaunay
polytopes
P arising
in
the
star
of
L.
Note
that
P is
always
generating
in
L (i.e.,
V(P)
generates
L)
with
the
exception
of
the
poly-
topes
as
and
(3s
that
are
not
generating
in
Es. For each
Delaunay
polytope
P,
we
present
its
I-skeleton
graph,
denoted
by
H(P)
and
called a
Delaunay
poly-
tope graph.
The
last
column
gives
the
square
r2
of
the
radius
r
of
the
sphere
circumscribing
P. As
dH(p)(u,
v)
=
~(u
-
v)2
for all
u,
v E
V(P)
(by
the
next
Proposition
14.3.3),
the
graphic
metric
space
(V(P),
dH(p))
of
the
graph
H(P)
is
hypermetric
and
its
associated
L-polytope
has
radius
~.
14.3
Delaunay
Polytopes
in
Root
Lattices
209
lattice
Delaunay polytope Delaunay polytope squared radius
L P
graph
Il(P)
r2
An
(n
;::
0)
see description
J(n
+
1,
above for 1
t~
Dn
(n
;::
4)
(jn
Knx2
1
lnn
~Il(n,
2)
n/4
Es
as
K9
8/9
/38
K8x2
1
E7
a7
Kg
7/8
3
21
G
a6
3/2
E6
221
G
27
4/3
Figure
14.3.1: Delaunay polytopes
in
the
irreducible
root
lattices
Remark
14.3.2.
We
group here several observations
about
the
graphs
J(n,
t),
!H(n,
2),
Knx2,
K
n
,
the
Schliifli
graph
G
27
,
and
the
Gosset
graph
G
56
occurring
in 14.3.1.
(i)
There
are some isomorphisms among
them,
namely,
J(n,
1) =
Kn,
~H(2,2)
K2,
2)
K
4
,
K
3X2
=
J(4,2),
K
4x2
=
~H(4,2).
Note
that
J(n,2)
coincides
with
the
line
graph
L(K
n
}
of
Kn,
which is also called
the
triangular
graph
and
denoted
by
T(n).
The
half-cube
graph
~H(5,
2)
is
also known as
the
Clebsch graph.
(ii)
J(n,t)
is
an
isometric
subgraph
of
~H(n,2)
and
of
J(n
+
1,t);
~H(n,2)
is
an
isometric
of
~H(n
+
1,2);
Knx2
is
an
isometric
subgraph
of
K(n+l)x2'
Also,
2)
is
an
isometric
subgraph
of
G
27
;
~H(6,
2),
K
6x
2,
J(8,2)
and
are isometric subgraphs of G
56
. Hence,
G27
is
an
isometric
subgraph
of (as G
27
has
diameter
2).
In
fact,
J(5,2)
(resp.
~H(5,2),
G
27
) is
the
subgraph
of
~H(5,2)
Crespo
ofG
27
,
G
56
)
induced
by
the
neighborhood
of
one
of
its
nodes.
(iii)
Jen,
t),
Knx2
(n
;::
2),
graphs.
2)
are
(i-graphs,
but
G
27
, G
56
are
not
(1-
I
We consider
in
the
next
result
an
interesting
property
for a Delaunay
polytope
P
in
a root lattice. Namely, a geometric feature of P is entirely
determined
by
210
Chapter
14.
Hypermetrics
and
Delaunay
Polytopes
the
metric
structure
of
P:
its
I-skeleton
graph
consists
of
the
pairs
of
vertices
at
squared
distance
2.
This
was proved
in
Deza
and
Grishukhin
[1993].
Proposition
14.3.3.
Let P
be
a generating Delaunay polytope in a root lattice.
Let
G(P)
denote the graph with set
of
vertices
V(P)
and with edges the pairs
(u,v)
for which d(2)(U,V) = 2, for
u,v
E
V(P),
and let
dG(p)
denote its path
metric. Then,
d(2)(U,V)
= 2d
G
(p)(u,v)
holds for all
u,v
E
V(P),
i.e., the Delaunay polytope space
(V(p),d(2))
co-
incides with the space
(V(P),2d
G
(p)). Moreover,
G(P)
coincides with the 1-
skeleton graph
H(P)
of
P,
i.e., two vertices u, v form an
edge
of
P
if
and only
if
d(2)(U,
v) = 2.
Proof. Let
u,v
E
V(P)
such
that
dG(p)(u,v) =
2.
Let (U,U1,V)
be
a
path
in
G(P)
from U
to
v, i.e., (u -
U1)2
=
(U1
- v)2 = 2
and
(u -
V)2
>
2.
Observe
that
(14.3.4)
Indeed,
(U1
-
u)T
(U1
- v)
:::::
0 since
any
three
vertices
of
P form a
triangle
with
no
obtuse
angles. Using
relation
(13.2.1),
we
obtain
that
(U1
-
U)T
(U1
- v) = 0,
l.
Moreover,
(u-v)2
=
4-2(U1-U)T(U1-V)
>
2,
implying
that
(U1-u)T(U1-V)
= 0
and,
thus,
(u - v)2 = 4 = 2d
G
(p)(u,v).
Consider
now
u,v
E
V(P)
such
that
dG(p)(u,v) = k
:::::
2.
Let
(uo
=
U,U1,
...
,Uk = v)
be
a
shortest
path
from u
to
v
in
G(P).
Then,
U - v =
2:1
<i<k
ri,
where
ri
:=
Ui
- Ui-1 is a
root
(i.e.,
rl
= 2) for 1
:S
i
:S
k. So
this
path
corresponds
to
the
sequence
of
roots
(r1,'"
,rk)'
Consider
the
subpath
(Ui-1,
Ui,
Ui+1).
Applying
(14.3.4),
we
deduce
that
r[
ri+1 = 0 holds. So,
any
two consecutive
roots
in
the
sequence
(r1,'"
, rk) are
orthogonal.
Note
that
w
:=
Ui-1
+
Ui+1
-
Ui
is also a
vertex
of
P since w
ELand
w also
lies
on
the
sphere
circumscribing
P.
Hence,
(UO,U1,
...
,Ui-1,W,Ui+1,
...
,Uk)
is
another
shortest
path
from U
to
v;
it
corresponds
to
the
sequence
of
roots
(r1,""
ri-1,
ri+1, ri,
ri+2,""
rk).
By
the
above
argument,
r[
ri+2
= (ri_1)T ri+1 =
O.
After
iteration,
we
obtain
that
any
two
roots
ri,
rjl
i
f-
j,
are
orthogonal.
Therefore,
(U-V)2=
L
r;=2k=2d
G
(p)(u,v)
l:S;;:'Ok
holds. Moreover, U - v is
the
diagonal
of
the
k-cube
spanned
by
rl,
...
,rk,
whose
vertices all
are
vertices
of
P. Therefore,
u,
v
do
not
form
an
edge
of
P.
It
is
easy
to
see
that,
conversely,
any
two vertices u, v
of
P
with
(u -
v)
2
= 2
form
an
edge
of
P.
I
We now see
that
Delaunay
polytopes
in
root
lattices
arise
in
a
natural
way
from
connected
strongly
even
hypermetric
spaces. Recall
that
a
distance
space
(X,
d)
is
strongly
even
if
d(i,j)
is
an
even integer for all
i,j
E X
and
d(i,j)
= 2
for
some
i,j
EX.
14.4
On
the
Radius of Delaunay Polytopes
211
Proposition
14.3.5.
Let
(X,
d)
be
a connected strongly
even
distance space.
If
(X,
d) is
hypermetric
with
associated
Delaunay
polytope
Pd
generating the lattice
Ld,
then
Ld
is a root lattice.
Proof.
Let i E X
f-+
Vi
E
V(Pd)
denote a representation of
(X,
d) in Ld. As
the
distance space
(X,
d)
is connected and strongly even, the lattice
Ld
is generated
by
the
set
{Vi
-
Vj
I
i,j
E X and
d(i,j)
2}.
Hence, Ld
is
a root lattice. I
As an application,
we
can
characterize the connected strongly even distance
spaces which are hypermetric, or iI-embeddable.
The
following Theorems 14.3.6
and
14.3.7
are
due, respectively, to Terwiliger and Deza
[1987J
and Deza and
Grishukhin
[1993]. An application to graphs will be formulated in Section 17.1.
Theorem
14.3.6.
Let
(X,
d)
be
a connected strongly
even
distance space.
The
following
assertions
are equivalent.
(i)
(X,
d) is
hypermetric.
(ii)
(X,
!d)
is an
isometric
subspace
of
a dire-et product
of
half-cube graphs
!H(n,2)
(n 2 7), cocktail-party graphs
Knx2
(n 2 7),
and
copies
of
the
Gosset
graph G56.
Proof.
(i) (ii) From Proposition 14.3.5, the Delaunay polytope
Pd
associ-
ated
with
(X,
d)
is generating in a root lattice. Therefore, from Proposition
14.3.3,
The
Delaunay polytope space
(V(Pd),
d~))
coincides
with
the
graphic
space
(V(Pd),
dH(Pd)) which, using Figure 14.3.1, is a direct
product
of Johnson
graphs, cocktail-party graphs, half-cube graphs, copies
of
G
27
and
G
56
•
The
result now follows using Remark 14.3.2.
The
implication (ii)
===>
(i) is obvious.
I
Theorem
14.3.7.
Let
(X,
d)
be
a connected strongly
even
distance space.
The
following
assertions
are equivalent.
(i)
(X,
d) is
isometrically
il-embeddable.
(ii)
(X,
~d)
is
an
isometric
subspace
of
a product
of
half-cube graphs
and
cocktail-party graphs. I
Theorem 14.3.7 can be proved in
the
same way as Theorem 14.3.6, using
Proposition
14.1.10
and
the
fact
that
the
graphs G
27
and G
S6
are not iI-graphs.
In
the
(main) subcase of graphic metric spaces, another proof was given by
Shpectorov
[1993];
it
is elementary (it does not use Delaunay polytopes)
but
longer.
We
will present
the
latter
proof in
Chapter
21.
14.4
On
the
Radius
of
Delaunay
Polytopes
We
present here several results which
in
some cases, a more precise informa-
tion
on
the
radius
of
Delaunay polytopes.
The
first result is a
partial
converse to
212
Chapter
14.
Hypermetrics
and
Delaunay
Polytopes
the
implication
(ii)
==*
(iv) from
Proposition
13.1.2;
it
gives explicitly
the
value
of
the
radius
of
the
spherical
representation
of
a
distance
space (X,
d)
of
nega-
tive
type
when
LiEX
d(i,j)
is a
constant.
This
result
was
already
formulated
in
Theorem
6.2.18;
we
repeat
it
here for convenience.
Proposition
14.4.1.
Suppose that
(X,
d)
is
of
negative type and that the
sum
LiExd(i,j)
does
not depend
onj
EX.
Then,
(X,d)
has a spherical represen-
tation, on a sphere whose center' is the center
of
mass
of
the representation and
whose radius
r is given
by
(14.4.2)
r2
=
_,1_,
L
d(i,j).
2 X
JEX
I
An
example
of
distance
space
with
constant
sum
LiEX
d(i,j)
is
the
graphic
metric
space (V(G), do),
where
G is a
distance
regular
graph
or
a
regular
graph
of
diameter
2;
see Section 17.2.
Proposition
14.4.3 below is a specification
of
Proposition
14.4.1
to
hypermetric
spaces,
and
Proposition
14.4.4 is a
partial
converse
to
the
implication
(i)
==*
(ii) from
Proposition
13.1.2.
Both
results
are
given
in
Deza
and
Grishukhin
[1993J.
Proposition
14.4.3.
Let
(X,
d)
be
a hypermetric space, let P
d
be
its associated
Delaunay polytope and let
r denote the radius
of
its circumscribed sphere
Sd.
If
LiEX
d(i,j)
does
not depend on j E
X,
then the radius r is given
by
rela-
tion (14.4.2).
Proof.
From
Proposition
14.4.1,
we
can
suppose
that
X lies
on
a
sphere
S
with
center
the
center
of
mass
of X
and
with
radius
r given by (14.4.2).
On
the
other
hand,
Sd
is a
minimal
dimension
sphere
containing
X.
Hence,
Sd
~
S holds.
The
affine space
spanned
by
Sd
contains
X
and
thus
its
center
of
mass, i.e.,
the
center
of
S.
Therefore,
Sand
Sd
have
the
same
radius. I
Proposition
14.4.4.
Let
(X,
d)
be
a connected strongly even distance space.
Suppose that
(X,
d)
has a representation on a sphere with radius r such that
r2
< 2. Then,
(X,
d)
is hypermetric.
Proof.
Let
(Vi
, i E
X)
be
a
representation
of
(X,
d)
on
a
sphere
S.
Up
to
translation,
we
can
suppose
that
Vi
= D for some
index
i E
X.
From
Proposition
14.3.5,
L(X,
d)
:=
Z(
Vi
, i E
X)
is a
root
lattice. We show
that
the
sphere
S is
empty
in
L(X,
d)
which,
by
Proposition
14.1.2, implies
that
(X,
d)
is
hypermetric.
Let
H
be
the
affine space
spanned
by
{Vi'
i E
X}.
We
can
suppose
that
S lies
in
H (else replace S
by
S n
H).
Let
£
be
the
line
in
R
n
+
1
orthogonal
to
H going
through
the
center
of S,
and
let q
be
a
point
on
£
such
that
(q
-
Vi)2
= 2 for all
i E
X.
Note
that
(q
- v)2 < 2 for each
point
v lying
in
the
interior of
the
ball
delimited
by
S.
Note
also
that
(q
- Vi)T(q - Vj) E
{D,
-1,
I}
for all i
=1=
j
EX.
14.4
On
the
Radius
of
Delaunay Polytopes
213
Indeed,
(Vi
-
Vj)2
is even since
(X,d)
is strongly even
and
(Vi
Vj)2
4 2(q Vi)T(q Vj) 4r2 <
8,
implying
that
(Vi
- Vj)2 E
{2,
4,
6}.
Therefore,
L'
Z( q -
Vi
liE
X) is a root
lattice
and, in particular, a
2
~
2 for each a E L', a
f.
O.
Suppose now
that
some point V E
L(X,
d) lies in
the
interior of
the
ball delimited by
S.
Then,
(v
-
q)2
< 2, yielding a contradiction
with
the
fact
that
v q E L'. I
\Ve
now present some results on spherical t-extensions
of
hypermetric spaces.
Given a distance space
(X,
d),
we
remind
that
its spherical t-extension
(X'
:=
X U {io}, spht (d))
is
defined by
spht(d)(i,j)
=
d(i,j)
spht(d)(i,
io)
= t
fori,j
EX,
for i E X.
The
next
lemma
characterizes
the
parameters
2
t for which spht(d) belongs
to
the
negative
type
cone
and
Proposition 14.4.6 below specifies values of t for which
the
spherical t-extension operation preserves hypermetricity. Both results are
taken from Grishukhin [1992b].
Lemma
14.4.5.
Let
(X,
d)
be
a distance space. Then, spht(d) E NEG
nH
if
and
only
if
(X,
d)
has a spherical representation with radius
rand
r2
:<;
t. Moreover,
(i)
If
r2
<
t,
then spht(d) has a spherical representation with radius R
:=
(ii)
If
t r2, then spht(d) has no spherical representation.
Proof.
If
sph
t
(
d)
E NEG
n
+1,
then
sph
t
(
d)
has a representation i E
X'
I-t
Vi
with
(Vi
Vio)2
t.
Hence,
the
Vi'S
(i E
X)
lie
on
the
sphere
So
with
center Vio
and
radius
Vi,
Let H denote
the
affine space spanned by
(Vi
liE
X).
Therefore,
the
Vi'S
(i E
X)
lie
on
the
sphere Sd 50 n H whose radius r is less
than
or equal
to
Vi,
Conversely, consider a representation
(Vi
liE
X)
of
(X,
d)
on
a sphere Sd
with
radius r such
that
r2
:<;
t. Consider
the
line orthogonal
to
the
affine space H
spanned
by
(Vi
liE
X)
and
going through
the
center
of
Sd' Choose a
point
Vio
on
this line which is
at
squared distance t r2 from
H.
Then,
(Vi
liE
X')
is a
representation
of
spht(d), which shows
that
spht(d) E NEG
n
+!.
Suppose r2 <
t.
Let 5 denote
the
sphere of dimension one higher
than
that
of
5d,
which contains Sd
and
Via'
So, Sd S n H
and
the
radius
of
Sis
R
:=
2..;Lr
2
'
On
the
other
hand,
if
r2
t, then
Vio
is
the
center of
So
=
Sd
and
the represen-
tation
of
spht(d)
is
not
spherical. I
Proposition
14.4.6.
Let
(X,
d)
be
a hypermetric space and let r denote the
radius
of
the sphere Sd circumscribing Pd.
2Note
that
the
quantity
min(
Jt
I
spht(d)
E
NEG,,+l)
is considered
in
approximation
theory
where
it
is called
the
Chebyshev radius
of
(X,d)
(Chebyshev [1947]).
214
Chapter
14. Hypermetrics
and
Delaunay Polytopes
(i)
Suppose
that
t
?::
21'2.
Then
8pht(d) is hypermetric, its radius is R
:=
2-Jt
t
_r
2
'
with t
?::
2R2
(and
R
?::
1', with equality
if
and only
if
t =
21'2).
Therefore,
sphf'(d)
is hypermetric
for
any integer m
?::
1.
Let
P
be
the
Delaunay
polytope associated with
spht(d).
If
t >
21'2,
or
if
t =
21'2
and
P
d
is
asymmetric,
then P is a
pyramid
with base Pd.
If
Pd
is centrally
symmetric,
then
P is a bipyramid with base Pd.
(ii)
If
1'2 < t <
21'2
and
if
Pd
is centrally
symmetric,
then spht(d) is
not
hypermetric.
Proof.
We
use the same
notation
as
in
the
proof
of
Lemma
14.4.5.
(i) Let
Ld
be the lattice spanned by
V(P
d
)
and
let L denote the lattice generated
by
Ld
and
Vio'
So, L consists
of
layers which are translates of Ld, the distance
between consecutive layers being
h =
~.
By
assumption, t
?::
implying
that
h
?::
R =
2vLr
2
'
This
shows
that
the sphere S is
empty
in
L. Therefore,
spht(d)
is
hypermetric
and
its associated Delaunay polytope P has radius
R.
If
t >
21'2,
then
P
is
the
pyramid
with
base
Pd
and
apex
Vio'
If
t
21'2,
then
one
checks easily
that
the
antipode
vio
of
Vio
on
the
sphere S belongs
to
L
if
and
only
if
Pd
is centrally symmetric. Therefore, if
Pd
is centrally symmetric,
then
P
is the bipyramid
with
base P
d
and
apex Vi;, and,
if
P
d
is asymmetric,
then
P is
the
pyramid
with
base P
d
and
apex
Vio'
Note
that
t > 2R2 follows from R A
and
h >
R.
(ii)
Let
V E
V(P
d
)
and
let v* be its antipode
on
the
sphere Sd.
Then,
w
v + v* -
Vio
belongs to L.
We
show
that
w lies inside
S,
which implies
that
8pht(d)
is
not
hypermetric. Indeed,
(v
from which
we
deduce
that
(w
c)2 = R2 +
2t
-
41'2
< R2.
I
We finally
mention
(without proof) a result from Deza
and
Grishukhin
[1996b] relating the covering radius
of
a lattice
to
the
radius
of
its
symmetric
Delaunay
polytopes.
Proposition
14.4.7.
Let
L
be
a
k-dimensional
lattice
in
I1Rk
with covering ra-
dius
p(L);
that is,
p(L)
is the
maximum
radius
of
(the sphere circumscribing)
a
Delaunay
polytope
in
L.
Let
R denote the
maximum
radius
of
a
symmetric
Delaunay
polytope
in
L (setting R
:=
0
if
none
exists) and let
l'
denote the
maximum
radius
of
a proper
symmetric
face
of
a Delaunay polytope
in
L.
If
!r2
:s;
R\
then
peL) R. Otherwise, R
Z
:s;
(p(L))2
:s;
!r2.
I
We now present some examples
of
applications (taken,
in
particular,
from
Avis
and
Maehara
[1994]
and
Grishukhin [1992b]).
Example
14.4.8.
Consider the complete
bipartite
graph
K1,n
and
its suspen-
sion
graph
'VK1,n'
Then,
their
path
metrics
can
be expressed
as
d(K1,n) =
14.4
On
the
Radius
of Delaunay Polytopes
215
sphl(d),
d(\1K
I
,n)
=
sph
l
(sphl
(d)), where d
:=
2d(Kn) takes value 2
on
all
pairs
of {I,
...
,n}.
The
distance d is hypermetric
with
radius
r =
In-;;1
(by
Proposition
14.4.3). Hence, using
Lemma
14.4.5,
we
obtain
that
d(K
n
,l)
has
a
spherical
representation
with
radius
R = 2v'Lr2 =
.Jii.
Therefore, d(\1 K
1
,n)
is
of
negative
type
if
and
only if n
:S
4.
Moreover, d(\1 K
n
,l) has no spherical
representation
if n = 4
and,
for n =
2,3,
d(\1 K l,n)
has
a spherical
representation
. h
d'
1 1 I
WIt
ra
IUS
2v'I-R2
=
v'4=Ti"'
Example
14.4.9.
Consider
the
graph
Kn
\
P3
for n
2:
4 (where
P3
denotes
the
path
on
3 nodes). Let d denote
the
distance on 3
points
with
two values equal to
2
and
one equal to 1. Clearly, d(K4 \ P
3
)
= Sphl
(d)
and
d(Kn \ P
3
)
=
sph~-3(d)
for n
2:
4.
One
can
easily verify
that
d
is
hypermetric
with
radius
r~
=
~
and
with
associated Delaunay polytope
0:2.
Set
for
n
2:
3.
Then,
27232522232
r4
=
12'
r5
=
5'
r6
=
8'
r7
=
3'
rs
=
4'
rg
= 1.
From
Lemma
14.4.5,
we
obtain
that
d(Kn \ P
3
)
has a spherical
representation
with
radius
rn if n
:S
9
and
that
d(KlO \ P
3
)
is
of
negative
type
but
has no spher-
ical representation. Fom
Proposition
14.4.4 applied to 2d(Kn \ P3),
we
obtain
that
d(Kn \
P3)
is
hypermetric
if
n
:S
8.
It
is
known
that
the
Delaunay
polytope
associated
with
2d(K7 \ P
3
)
is
the
Schliifli polytope
221
and
that
the
Delaunay
polytope
associated
with
2d(Ks \
P3)
is
the
Gosset
polytope
321
(see Section
16.2). Hence,
Proposition
14.4.6 yields
that
d(Kg \ P
3
)
is
not
hypermetric
(since
321
is centrally symmetric). Finally, note
that
d(Kn \ P
3
)
is e
1
-embeddable
if
n
:S
6
but
not
for n =
7.
This
latter
statement
will be justified
later
in
Remark
19.2.9. I
At
this
point
let us observe
as
a curiosity
an
analogy
between
the
minimum
l'1-size
and
the
radius
of
the
Delaunay
polytope
associated
to
an
l'1-embeddable
distance.
Let
(X,
d)
be
a
distance
space
with
IXI
= n
and
consider
the
iterated
spherical
t-extension
sph;"(d)
of
d.
Part
of
Proposition
14.4.6
can
be
rephrased
as follows:
(a)
Suppose
d E
HYP
n
.
Then,
sph;"(d)
E
HYP
n
+
m
for all m
2:
1 if t
2:
~(diam(Pd))2,
where
diam(Pd)
denotes
the
diameter
of
the
sphere
circumscribing
the
Delaunay
poly-
tope
P
d
associated
with
d.
Compare
(a)
with
Lemma
7.3.3, which
states:
(b)
Suppose
d E
CUT
n
•
Then,
sph;"(d)
E
CUT
n
+
m
for all m
2:
1 if t
2:
~s",(d),
where
s'"
(d)
denotes
the
minimum
l'1-size
of
d.
Observe,
moreover,
that
the
limit value of
(diam(P
sph
;"(d)))2 in (a)
and
of
S'"
(sph;" (d))
in
(b)
is
equal
to
2t
when m goes
to
infinity.
216
Chapter
14.
Hypermetrics
and
Delaunay Polytopes
Example
14.4.10.
Set
d:=
d(Kn). Then, d
is
hypermetric with radius
(by Proposition 14.4.3). Then,
n-l
spht(d) E NEG
n
+1
~
t 2
~
(by
Lemma
14.4.5 (i))
and
it
is
easy to check
that
I
Example
14.4.11.
Set d d(Knx2)' Then,
dis
hypermetric with radius
~
(by Proposition 14.4.3). One
can
check
that,
for each m 2 1,
sphr'(d)
E
MET
n
+
11l
(or
CUT
n
+
m1
or
HYP
n
+
m
)
~
t
21.
(Apply Proposition 14.4.6 (i)
and
relations (a),(b) above, after noting
that
8£1
(d)
= 2.) I