Deza M.M., Laurent M. Geometry of Cuts and Metrics

M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,

DOI 10.1007/978-3-642-04295-9_15, © Springer-Verlag Berlin Heidelberg 2010

Chapter

15.

Delaunay

Polytopes:

Rank

and

Hypermetric

Faces

There

is a

natural

notion

of

rank

for

hypermetric

spaces. Namely,

if

(X,

d)

is

a

hypermetric

space,

then

its

rank

rk(X,

d)

is defined as

the

dimension

of

the

smallest

face

of

the

cone

HYP(X)

that

contains

d.

The

extremal

cases

when

the

rank

of

(X,

d)

or

its

corank

is

equal

to

1 correspond, respectively,

to

the

cases

when

d lies

on

an

extreme

ray

or

on

a facet

of

HYP(X).

Correspondingly,

the

rank

rk(P)

of

a

Delaunay

polytope

P is defined as

the

rank

of

its

Delaunay

polytope

space

(V(P),

d(2)).

Delaunay

polytopes

of

rank

1

are

called extreme;

they

are

associated

to

hypermetrics

lying

on

an

extreme

ray

of

the

hypermetric

cone.

This

notion

of

rank

for a

Delaunay

polytope

P

has

the

following geometric

interpretation:

It

coincides

with

the

number

of

degrees

of

freedom one

has

when

deforming

P

in

such

a way

that

the

deformed

polytope

remains

a

Delaunay

polytope;

a precise

formulation

can

be

found

in

Theorem

15.2.5.

Extreme

Delaunay

polytopes

have a highly rigid geometric

structure;

indeed,

their

only

affine

transforms

which are still

Delaunay

polytopes

are

their

homoth-

etic

transforms

(see Corollary 15.2.4).

The

first

example

of

an

extreme

Delaunay

polytope

is

the

segment

0;1,

associated

with

the

cut

semimetrics.

Other

examples

are

known,

such

as

the

Schliifli

polytope

221,

the

Gosset

polytope

3

21

constructed

from

the

root

lattice

Es

and

some

others

constructed

from

the

Leech

lattice

A24

and

the

Barnes-Wall

lattice

A

16

;

they

will

be

described in

the

16.

Delaunay

polytopes

of

corank 1, which

correspond

to

facets

of

the

hyperme-

tric

cone,

are

well

understood;

they

are

the

repartitioning

polytopes

considered

by

Voronoi (see Section 15.2).

In

Section

15.1,

we

study

several

properties

for

the

notion

of

rank

of

a De-

launay

polytope;

in

particular,

its

invariance

under

taking

generating

subspaces

(see

Theorem

15.1.8)

and

its

additivity

with

respect

to

the

direct

product

of

polytopes

(see

Proposition

15.1.10). We

present

in

Section 15.3 some

bounds

for

the

rank

of

a

Delaunay

polytope

in

terms

of

its

number

of

vertices (see Proposi-

tion

15.3.1). We also investigate

in

detail

in

Section 15.2

the

links

between

faces

of

the

hypermetric

cone

and

their

associated

Delaunay

polytopes.

15.1

Rank

of

a

Delaunay

Polytope

We consider here

the

notion

of

rank

for a

Delaunay

polytope;

we

follow essentially

Deza,

Grishukhin

and

Laurent

[1992], where

this

notion

was

introduced

and

218

Chapter

15. Delaunay Polytopes:

Rank

and

Hypermetric

Faces

studied.

Let

(X,

d)

be a

hypermetric

space.

We

define

its

annullator1

Ann(X,

d)

by

Ann(X,d)

=

{b

E

ZX

I b

=I-

ei

for i E

X,

L

bi

=

1,

L

bibjd(i,j)

=

O}.

iEX

i,jEX

Let

S(X,

d)

denote

the

system

which consists of

the

equations:

L bibjX(i,j) = 0 for

bE

Ann(X,

d);

i,jEX

that

is,

S(X,

d)

consists

of

the

hypermetric

inequalities

that

are satisfied

at

equality

by

d.

Let

F(X,d)

(or

F(d))

denote

the

smallest (by inclusion) face of

the

hypermetric

cone

HYP(X)

that

contains

d.

Hence,

F(X,

d)

=

HYP(X)

n n

Hb,

bEAnn(X,d)

where

Hb

denotes

the

hyperplane

in

~(I~I)

defined by

the

equation:

L

bibjx(i,j)

=

O.

i,jEX

The

dimension

of

F(X,

d)

is

equal

to

the

rank

of

the

solution set

to

the

system

S(X,

d).

Definition

15.1.1.

(i) The

rank

rk(X,

d)

of

a hypermetric space

(X,

d)

is defined

as

the dimension

of

the smallest face

F(X,

d)

of

HYP(X)

that contains

d.

Its

corank

is

defined

as

(I~I)

-

rk(X,

d).

(ii) The

rank

rk(P)

of

a Delaunay polytope P is defined

as

the rank

of

the

Delaunay polytope space

(V(P),

d(2)), i.e.,

rk(P)

:=

rk(V(P),

d(2)). A De-

launay polytope

of

rank 1 is called extreme.

Hence,

rk(X,

d)

= 1 if d lies

on

an

extreme

ray

of

the

hypermetric

cone;

rk(X,

d)

=

(I~I)

if d lies

in

the

interior of

HYP(X),

i.e.,

F(X,

d)

=

HYP(X);

and

rk(X,

d)

=

(I~I)

- 1 if

F(X,

d)

is a facet of

HYP(X).

In

fact,

the

rank

of a

hypermetric

space is

an

invariant of

its

associated

Delaunay

polytope; namely,

rk(X,

d)

=

rk(P

d

)

holds (see Corollary 15.1.9).

In

order

to

prove

this

invariance result,

we

need

to

investigate some

properties

of

the

system

S(X,

d)

of

hypermetric

equalities satisfied by

d.

We first observe

that

a

hypermetric

space

and

any

gate

O-extension

of

it

have

the

same

rank.

This

means

that

we

may

consider only metrics

rather

than

semimetrics. Let

(X,

d)

be

a

distance

space

and

io

E

X,

jo

if-

X.

Let

(X'

:=

IThis

notion

was

already

used

in

the

proof

of

Theorem

14.2.1.

15.1

Rank

of

a Delaunay Polytope

219

Xu

{jo},d')

be

its

gate

O-extension, defined by d'(io,jo) =

0,

d'(i,jo) = d(io,i)

for i E

X,

and

d'(i,j)

=

d(i,j)

for

i,j

EX.

Lemma

15.1.2.

Let

(X',

d')

be

a gate O-extension

of

the hypermetric space

(X,

d). Then,

rk(X',

d') =

rk(X,

d).

Proof.

Suppose

that

(X',

d') is defined as above.

We

show

that

the

solution

sets

of

the

systems

S(X,

d)

and

S(X',

d')

have

the

same

rank.

Since

S(X,

d)

is a

subsystem

of

the

system

S(X',

d'),

it

suffices

to

check

that

each

additional

variable

x(i,jo)

(i E

X)

in

the

system

S(X',d')

can

be

expressed

in

terms

of

the

variables

x(i,j)

(i,j

E

X).

As d(io,jo) =

0,

the

triangle equalities

x(io,i)-

x(jo,i)

- x(io,jo) = 0

and

x(jo,i)

-

x(io,i)

- x(io,jo) = 0 belong to

the

system

S(X',

d').

This

implies

that

the

equality x(jo, i) = x(io, i) (i E

X)

follows from

S(X',

d'). I

Let

P

<;;:

]K.k

be

a k-dimensional Delaunay

polytope

with

set of vertices

V(P)

and

let V

<;;:

V(P)

be

a generating subset of

V(P).

For w E

V(P),

every a E

ZV

such

that

w = L avv

and

L a

v

= 1 is called

an

affine realization of w in the

vEV

set V.

Proposition

14.1.5 implies

that,

for b E

ZV

with

LVEV b

v

=

1,

bE

Ann(V,

d(2))

{=?

L

bvv

E

V(P).

vEV

In

other

words,

there

is a one-to-one correspondence between

(i)

the

equations

of

S(V,

d(2)),

and

(ii)

the

affine realizations

of

the

vertices

of

P

in

the

set

V.

In

particular,

if B is a basic set

in

V(P),

then

each vertex has a unique affine

realization

in

the

set B

and,

therefore,

S(B,

d(2))

is a

system

of

IV(P)

\

BI

=

IV(P)I

- k - 1 equations

in

(k!l) variables. Therefore,

(15.1.3)

Lemma

15.1.4.

Let V

be

a generating subset

ofV(P)

and let c E

ZV

such that

LVEV

C

v

= 0 and LVEV

CvV

=

O.

The following equations:

(15.1.5)

L

cvx(u,v)

= 0 for U E

V,

vEV

(15.1.6)

L Cucvx(u,v) = 0

u,vEV

are

implied

by

the system S(V,

d(2)).

220

Chapter

15. Delaunay Polytopes:

Rank

and

Hypermetric

Faces

Proof.

Let

1L

E V

and

c' E

ZV

be

defined by

c~

:=

Cu

+ 1,

c~

:=

C

v

for v E

V\

{u}.

Hence, c' is

an

affine realization

of

u in

V.

Therefore,

the

equation:

L

c~c~x(v,w)

= 0

v,wEV

belongs

to

the

system

S(V,

d(2)).

It

can

be

rewritten

as

L cvcwx(v,w) + 2 L

cvx(u,v)

=

O.

v,wEV

vEV

By

multiplying

the

above equality by C

u

and

summing

over u E V, we

obtain

(15.1.6). Hence,

the

equation

(15.1.6) follows from S(V,d(2))

and,

thus,

the

equations

(15.1.5) as well. I

For

each w E

V(P),

let a

W

E

ZV

be

a given affine realization

of

w

in

the

set

V.

Let

S'(V,

d(2))

denote

the

system

consisting of

the

equations

(15.1.5)

and

(15.1.6)

together

with

the

hypermetric

equations:

L

a~a~x(u,v)

= 0 for

wE

V(P).

u,vEV

Lemma

15.1.7.

The systems

S(V,

d(2))

and

S'(V,

d(2))

have the same solutions.

Proof.

It

remains

only

to

show

that

each

equation

of

S(V,

d(2))

follows from

the

system

S'(V,

d(2)).

Let

W E

V(P)

and

let b

be

another

affine realization

of

w

in

V.

Then,

we

can

apply

(15.1.6)

with

c

:=

a

W

-

b,

which yields

L

(a~

-

bu)(a~

-

bv)x(u,v)

=

0,

i.e.,

u,vEV

u,vEV u,vEV

We check

that

the

first two

terms

in

the

above equality are equal

to

zero, which

will

imply

that

the

equation:

L bubvx(u, v) = 0

u,vEV

follows from

the

system

S'(V,

d(2)). Indeed,

the

first

term

is equal

to

0, since

it

corresponds

to

an

equation

of

S'(V,d(2)).

On

the

other

hand,

for u E

V,

the

equation:

L

a~x(u,v)

= L

bvx(u,v)

vEV vEV

follows from (15.1.5). Hence,

the

second

term

is equal

to

-2

L

a~a~x(u,v)

=

O.

I

u,vEV

15.1

Rank

of

a Delaunay Polytope

221

Theorem

15.1.8.

Let

P

be

a

Delaunay

polytope

and

let V

be

a generating

subset

of

V(P).

Then,

Proof.

We show

that

the

solution sets

to

the

systems

S(V,

d(2))

and

S(V(P),

d(2))

have

the

same

rank.

Since

S(V,

d(2))

is

a

subsystem

of

the

system

S(V(P),

d(2)),

it

suffices

to

check

that

each variable

x(

w,

w')

((

w,

w')

E

(V

x

(V(P)

\

V))

u

(V(P)

\

V)2)

can

be expressed

in

terms

of

the

variables

x(

u,

v)

(u, v E

V).

Let

w,

w'

E

V(P)

\ V

and

let a, a' denote affine realizations

of

w,

w'

in

V,

respectively. We show

that

the

following equations (a)

and

(b) are implied by

S(V(P),

d(2)):

(a)

(b)

x(w,u)

=

Lavx(u,v)

for

uEV,

vEV

x(w,w')

= L

aua~x(u,v).

u,vEV

For this, let

b,

b'

E ZV(P) be defined by b

w

:=

-1,

b

v

:=

a

v

for v E V

and

b

v

:=

0 for v E

V(P)

\

(V

u

{w}),

b~,

:=

-1,

b~

:=

a~

for v E V

and

b~

:=

0 for

v E

V(P)

\

(V

u {w'}). We

can

apply

Lemma

15.1.4. From (15.1.5),

we

obtain:

L

bvx(u,

v)

=0

foralluEV,

vEV(P)

which implies (a). Applying (15.1.6) for

b,

b'

and

b + b',

we

obtain:

This

implies:

L bubvx(u,

v)

=0,

L

b~b~x(u,v)=O,

u,vEV(P) u,vEV(P)

L

(b

u

+

b~)(bv

+

b~)x(u,v)

=

O.

u,vEV(P)

L

bub~x(u,v)

=

o.

u,vEV(P)

Expressing

b'

in

terms

of

a'

and

b in

terms

of

a in

the

latter

equality,

we

obtain:

x(w,w')

- L

aux(u,w')

- L

a~x(w,v)

+ L

aua~x(u,v)

=

o.

uEV

vEV

u,vEV

The

second

and

third

terms

in

the

above equality are equal

to

x( w,

w')

by (a).

This

shows

that

(b) holds. I

Corollary

15.1.9.

Let

(X,

d)

be

a

hypermetric

space with associated

Delaunay

polytope Pd. Then,

rk(X,

d)

= rk(Pd).

222

Chapter

15. Delaunay Polytopes:

Rank

and

Hypermetric Faces

Proof. Let V

~

V(Pd)

representing

(X,d).

Then,

rk(X,d)

rk(V,d(2») by

Lemma

15.1.2

and

rk(V,d(2») =

rk(P

d

)

by

Theorem

15.1.8 as V generates

V(Pd).

I

We

conclude

this

section

with

an

additivity

property

of

the

rank

of

a Delaunay

polytope.

Proposition

15.1.10.

Let

PI

and

P

2

be

Delaunay polytopes.

Their

direct

product

PI

x

P2

is a Delaunay polytope with rank

rk(P

l

x

P2)

=

rk(P

I

)

+

rk(P

2

).

I

For instance,

rkbk)

= k for

the

hypercube

'Yk,

since

'Yk

is

the

direct

product

('Yd

k

and

rkbl)

=

1.

15.2

Delaunay

Polytopes

Faces

15.2.1

Hypermetric

Faces

We

show

that

hypermetrics

that

lie

in

the

interior

of

the

same

face

of

the

hyper-

metric cone are associated

with

affinely equivalent Delaunay polytopes; therefore,

one

can

speak

of

the Delaunay

polytope

associated

with

a face

of

the

hypermetric

cone.

This

result

is presented in Theorem 15.2.1 below;

it

was proved by Deza,

Grishukhin

and

Laurent

[1992J.

Let

T

be

an

affine bijection

of

JR?k.

For u, v E

JR?k,

set

dT(

u,

v)

:=

(T(

u)

T(

v

»)2.

Theorem

15.2.1.

Let

P

~

JR?k

be

a Delaunay polytope and let V

be

a generating

subset

of

V(P).

Let

T

be

an

affine bijection

of

JR?k.

Let

F denote the

smallest

face

of

the

hypermetric

cone

HYP(V)

that

contains (V, d(2».

(i)

If

T(P)

is a

Delaunay

polytope,

then

dT lies

in

the

interior

of

F,

i.e.,

F(dT) = F.

(ii)

Let

d E

HYP(V).

If

d lies

in

the

interior

of

F,

then

the

Delaunay

polytope

P

d

associated with d is affinely equivalent to

P.

Proof. (i)

Let

b E

ZV

with

b

v

=

1.

We

show

that

L

b"bv(T(u)

T(v»2

= 0

~

L b"bv(u - v)2 =

o.

u~EV

u,vEV

For

this,

let

c, T (resp.

CT,

TT) denote

the

center

and

radius

of

the

sphere circum-

scribing

P (resp.

T(P»).

Then,

L

b"bv(T(u)

T(v»2

2(rT)2 -

2(L

buT(u)

CT)2,

u,vEV

15.2 Delaunay Polytopes Related

to

Faces

223

which is equal

to

0 if

and

only if buT( u) is a vertex of

T(P).

On

the

other

hand,

u,vEV

is equal

to

0

if

and

only if

buu

is a vertex of P.

The

result now follows as

2::

buT(u)

T(2::

buu)

uEV

is a vertex of

T(P)

if

and

only if

EUEV

buu

is a vertex of P, since T is

an

affine

bijection.

This

shows

that

d

T

lies in

the

interior of

the

face

F.

(ii) Let

Pd

be

the

Delaunay polytope associated

with

d

and

let T : V -----> V(Pd)

be

a generating

mapping

such

that

d(u, v) (T(u) - T(v))2 for

u,v

E

V.

The

mapping

T

is

one-to-one since d(u, v)

=/;

0 for u

=/;

v E

V.

We

show

that

T

can

be

extended

to

an

affine bijective

mapping

of

the

space spanned by

V,

mapping

Yep)

to

V(Pd)'

First,

we

verify

that

T preserves

the

affine dependencies on

V,

i.e.,

that

if

c E

ZV

with

C

v

=

0,

then

2::

CvV

0

<=}

2::

CvT(v) =

O.

vEV

Since all

the

vectors v E V lie on a sphere

and

the

same holds for

their

images

T(v),

we

have:

(a)

2::

CuCvd(2)(U,

v) =

2::

Cu

c

v(U-V)2=-2(2::c

v

v)2,

u~EV

u,vEV

vEV

u,vEV

-2

(2::

cvT(V))

2

vEV

(b)

2::

Cucvd(u,

v) =

2::

CuCv(T(u)

- T(v))2

By

assumption, F(d) =

F,

i.e.,

the

systems S'(V,d)

and

S'(V,d(2)) have

the

same

sets of solutions (using

Lemma

15.1.7). This implies

that

the

quantities in

(a)

and

(b) are simultaneously equal

to

zero.

vVe

now check

that,

for b E

ZV

with

b"

= 1,

2::

bvv

is a vertex of P

<=}

2::

bvT(v) is a vertex of

Pd.

vEV

But,

by Proposition 14.1.5,

equation

Eu,vEV

bubvx(

U,

v)

satisfies

the

same

equation.

by V by

setting

EVEV

bvv

E

yep)

if

and

only if

d(2)

satisfies the

o and bvT(v) V(Pd)

if

and

only if d

Therefore,

we

can extend T

to

the

space spanned

T(2::

bvv)

2::

bvT(v);

vEV

T is affine bijective

and

maps P

on

Pd.

I

224

Chapter

15. Delaunay Polytopes: Rank

and

Hypermetric Faces

Corollary

15.2.2.

Let

(X,

d)

and

(X,

d')

be

two

hypermetric

spaces with asso-

ciated

Delaunay

polytopes P

d

and

Pdf.

Let

F(d)

and

F(d')

denote

the

smallest

faces

of

HYP(X)

that contain d

and

d', respectively.

If

F(d)

=

F(d'),

then

Pd

and

Pdf

are affinely equivalent.

Proof.

If

d(i,j)

=1=

0 for all i

=1=

j E

X,

then

(X,d)

is isomorphic to a subspace

(V,d(2)) of

(V(P

d

),d(2»),

where V is a generating subset of

V(Pd).

As

£1'

lies in

the interior of

F(d),

Theorem 15.2.1 (ii) implies

that

Pdf

is affinely equivalent to

Pd. Otherwise, note

that

d( i,

j)

0

if

and only if d' (i,

j)

= 0 as d, d' satisfy the

same triangle equalities since

F(d)

F(d').

Hence, X can be partitioned into

Xl

U

...

U Xm for m <

IXI

in such a way

that,

for

i

=1=

j

EX,

d(i,j)

=

d'(i,j)

= 0

if

and

only if

i,j

E X

h

for some

hE

{I,

...

,

m}.

Let

Xl

E

Xl"'"

Xm

E Xm

and

denote by

do

(resp.

d~)

the projection of

£1

(resp.

£1')

on

Xo

:=

{x\,

...

,x

m

}.

One

can easily see

that

£1

0

,£16

lie in the interior of the same face

of

HYP(X

o

)

which, by

the

above argument, implies

that

P

d

and

Pdf

are affinely equivalent

(as

do

is associated to the same Delaunay polytope P

d

as

£1

and

db

is associated

to

Pdf). I

Remark

15.2.3.

The implication from Corollary 15.2.2 is strict, in generaL

Indeed,

it

is easy to construct examples of hypermetrics

£1,

d' E

HYP(X)

whose

associated Delaunay polytopes are affinely equivalent,

but

lying on distinct faces

of

HYP(X),

i.e., such

that

F(d)

=1=

F(d').

For instance, any two distinct

cut

semimetrics

8(8),

8(T) are associated to the same Delaunay polytope, namely

al,

but

they lie on distinct faces as each

cut

semimetric lies on

an

extreme ray

of

HYP(X).

Another example

can

be easily obtained by taking a generating

subset

V

:=

{Vl," . , v

n

}

of a Delaunay polytope P

and

considering the hyper-

metrics

d,d' E HYPn defined by

d(i,j)

(Vi -

Vj)2,

d'(i,j)

(Vu(i)

vu(j))2

for

i,j

E

{I,

...

,

n},

where (J" is a

permutation

of

{I,

...

, n}. I

Corollary

15.2.4.

Let

P

be

a Delaunay polytope

in

JIl&k.

Then, P is

extreme

if

and

only

if

the only {up to orthogonal transformation and translation} affine

bijective

transformations

T

of

JIl&k

for

which

T(P)

is a Delaunay polytope are the

homotheties

2

•

Proof. Suppose first

that

rk(P)

=

1,

i.e.,

that

(V(P),

d

(2

»)

lies on

an

extreme

ray

of

HYP(V(P)).

Assume

that

T(P)

is a Delaunay polytope. By Theo-

rem

15.2.1 (i), d

T

)..2d

e2

) for some scalar

>...

Hence, (T(u) _T(v))2 >..2(u-v?

for all u, V E

Yep).

It

is not difficult to see

that,

up to translation,

>..

-IT

is an

orthogonal transformation.

Suppose now

that

the only affine bijective transformations T for which

T(P)

is

a Delaunay polytope are the homotheties. Let

£1

E

HYP(V(P)

with

F(d)

F(d

C2

).

By Theorem 15.2.1 (ii), the Delaunay polytope

Pd

associated to

£1

is

of the form

>"P,

where>.. >

0,

implying

that

d =

>..2d

(2

).

This shows

that

homothety is a

mapping

T :

__

:'IRk

such

that

Tex}

;:

Ax

for all x E

JIl&k,

for some

A #

O.

15.2

Delaunay

Polytopes

(V(P),

d(2»)

lies

on

an

extreme ray

of

HYP(V(P)),

i.e.,

rk(P)

=

1.

I

Let P be a k-dimensional Delaunay polytope

in

Rk. Let

T(P)

denote

the

set

of affine bijections T

of

Rk

(taken

up

to

translations

and

orthogonal

transforma-

tions) for which

T(P)

is

again a Delaunay polytope.

If

P has

rank

1

then,

by

Corollary 15.2.4,

T(P)

consists only of homotheties

and,

hence, its dimension

is also equal to

1.

This

fact

can

be generalized for

arbitrary

ranks, as

the

from

Laurent

[1996a] shows.

Theorem

15.2.5.

For

a Delaunay polytope

P,

the dimension

of

the set

T(P)

(in the topological sense) is equal

to

the rank

of

P.

Proof. We

can

suppose

without

loss of generality

that

P is a k-dimensional

Delaunay

polytope

in

Rk

which contains

the

origin as a vertex. Let V denote

the

set

of

vertices of

P,

let dp denote

the

associated distance

on

V defined by

dp(u,v):=

(u -

v?

for all

u,v

E

V,

and

let

Fp denote

the

smallest face of

the

hypermetric cone

HYP(V)

that

con-

tains

dp. Denote by To(P)

the

set of nonsingular k x k matrices A for which

the

polytope

A(P)

:=

{Ax

I x E

P}

is again a Delaunay polytope. Clearly,

the

sets

T(P)

and

To(P)/OA(k)

coincide. (Here,

To(P)/OA(k)

denotes

the

quotient

set

of

To(P) by

the

set OA(k) of orthogonal matrices of order k.)

We

show

that

the

dimension of

the

set

To(P)/OA(k)

is equal to

the

rank

of P. For

this

we

need

to

introduce

an

intermediary

cone

Cpo

As

the

hypermetric

cone

HYP(V)

is polyhedral,

we

can

suppose

that

it is

defined by

the

hypermetric

inequalities

I:u,vEV,u<v

bubvxuv

sO

for b E B, where

B is a finite subset of

{b

E

ZV

I

I:uEV

b

u

= I}. Let A denote

the

subset of B

corresponding to

the

hypermetric equalities defining

the

face Fp;

that

is, b E A

if

I:u,vEV

bubv(u -

v)2

=

O.

Let us now introduce

the

cone

Cp

which consists of

the

symmetric

k x k positive semidefinite matrices M satisfying:

(a) L

bubv(u-V)TM(u-v)

sO

forbEB\A,

u,vEV

(b)

L bubv(u - v)T

M(u

- v) = 0 for b E A.

u,vEV

Then

the

relative interior of

the

cone C p consists of

the

positive definite matrices

M satisfying (b),

and

(a)

with

strict

inequality.

We

claim

that

(c)

The

dimension of

the

cone C p is equal to

the

rank

of

P.

Indeed, set s

:=

rk(P)

and

t

:=

dim(Cp). Let dI,

...

,d

s

be linearly

independent

points

lying

in

the

relative interior of

the

face Fp. Applying

Theorem

15.2.1 (ii)

we

obtain

AI,

...

,As

E To(P) such

that

di(U,V) =

(u

-

vl

A[

Ai(U - v) for

all

u, v E V

and

i =

1,

...

, s.

Then,

Af

A

l

,

...

,

A;

As are linearly

independent

226

Chapter

15. Delaunay Polytopes:

Rank

and

Hypermetric Faces

members of

the

cone Cp, which shows

sst.

Conversely, let MI,

...

, M

t

be

linearly independent

and

lying in

the

relative interior of

Cpo

As each

Mh

is

positive definite, it is of

the

form

AI

Ah for some k x k nonsingular

matrix

A

h

. Set dh(U,V)

(u

V)TMh(U - v) =

(AhU

- AhV)2 for

u,v

E V

and

h = 1,

...

, t.

Then,

the

points

db'"

,tit lie in

the

relative interior

of

the

face

Fp. Moreover, they are linearly independent, which shows

that

t S

s.

Hence,

s = t

and

(c) holds. (Indeed, suppose

E~=l

Ahdh

= 0 for some scalars

Ah.

Then,

(u -

7))T

(E~=l

AhMh)( U v) 0 for all u, v E

V.

As V is full-dimensional

and

contains

the

origin, this implies easily

that

E~=I

AhMh = 0 and, thus,

Ah

0

for all

h.)

We

can

now formulate a homeomorphism (=bicontinuous bijection) between

the

set To(P)/OA(k)

and

the

relative interior of the cone

Cpo

Namely, consider

the

mapping

(J:A

......

ATA.

Then,

(J

establishes clearly a one-to-one correspondence between To{P)/OA{k)

and

the

relative interior of

Cpo

The

result now follows as

(J

is

a homeomorphism

between,

on

the

one hand, the quotient set of

the

set

of k x k matrices by

the

equivalence relation:

A",

B

if

ATA

and, on

the

other

hand,

the

set of

k x k positive semidefinite matrices. I

15.2.2

Hypermetric

Facets

Following A vis

and

Grishukhin [1993J,

we

now describe

the

Delaunay polytopes

which are associated

with

the

facets of

the

hypermetric cone.

Let

~h

~2

be

two simplices lying in affine spaces

that

intersect

in

one point

which belongs

to

~l

n~2.

Then,

their convex hull P

Conv(~l

U~2)

is

called

a repartitioning polytope.

This

polytope was studied

by

Voronoi [1908, 1909].

There

is only one affine dependency among

the

vertices

of

~1

and

~z;

namely,

~

bvv

~

bvv,

VEVI

VE

V

2

where b

v

=

EVE

V

2 b

v

=

1,

b

v

?::

0 for v E VI U V

z

,

and

V;

denotes

the

set

of vertices

~i,

i

1,2.

Set

Vo

:=

{v E VI U

V2

I b

v

=

O}.

Then,

PI

:=

Conv(V1 U V

2

\

V

o

)

is also a repartitioning polytope,

with

the

same affine dependency between its

vertices as

P

and

P =

II

Pyrv(Pt}.

vEVo

We

denote

the

repartitioning polytope P by

P~,

where m =

IVoI,

p+

1 = IVI \

Vol

and

q + 1

1V2

\

Vol.

P~

has

m + p + q + 2 vertices (if

p,q

?::

1)

and

its

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.