NANZAN-TR-2009-05

A Note on M-convexity
in Polyhedral Split Decomposition of Distances
Shungo Koichi

November 2009

Technical Report of the Nanzan Academic Society
Information Sciences and Engineering

A Note on M-convexity
in Polyhedral Split Decomposition of Distances∗
Shungo Koich†November 2009

Abstract
The polyhedral split decomposition, introduced by Hirai, is a decomposition of apolyhedral convex function into a sum of split functions and the residue, where a split
function is a polyhedral convex function whose value at a point is defined to be thedistance between the point and a hyperplane. The polyhedral split decomposition,
applied to the convex extension of a metric, is known to obtain Buneman’s decomposition of a metric geometrically. In this paper we shed a light on this fact fromdiscrete convex analysis, by observing that this is a decomposition of an M-convex
function into a sum of M-convex functions, whereas a sum of M-convex functions is
not necessarily M-convex in general. We discuss the reason why the M-convexity ispreserved in this polyhedral split decomposition. By applying the polyhedral split
decomposition to a quadratic M-convex function, we also observe that a quadratic
M-convex function induces a lattice dicing or, equivalently, a zonotope which fills
the space facet-to-facet by its translations. Inspired by a result on lattice dicings,
we propose another canonical representation of a quadratic M-convex function as apositive combination of rank one forms.
Keywords: M-convex function, polyhedral split decomposition, tree metric,
split-decomposability, lattice dicing.

1

Introduction

A tree metric is known to be representable as a sum of split metrics. In [7], this classicalresult is reobtained geometrically via the polyhedral split decomposition of a metric. In
this paper we intend to shed light on this decomposition from discrete convex analysis
advocated by Murota [9].
To review the previous results, we begin by classifying a distance, metric, tree metricand split metric on a finite set X. A distance is defined as a function d : X × X → R
such that d(i, i) = 0 for all i ∈ X and d(i, j) ≤ d(i, k) + d(k, j) for all i, j, k ∈ X.
A metric d is a symmetric and nonnegative distance, that is, a distance d such thatd(i, j) = d(j, i) ≥ 0 for all i, j ∈ X. A metric d is called a tree metric if there exits a treewith nonnegative edge lengths such that d(i, j) is equal to the length of the path in thetree between the vertices indexed by i and j for all i, j ∈ X. An X-split is a partition∗

This is a substantial revision of the authors’ technical report “Polyhedral Split Decomposition of Distances from the Viewpoint of Discrete Convex Analysis”, METR 2007–11, Depertment of Mathematical
Informatics, University of Tokyo, 2007.
†
Department of Systems Design and Engineering, Nanzan University, Seireicho 27, Seto 489-0863,
Japan. shungo@nanzan-u.ac.jp

1

of X into two nonempty sets, i.e., a pair {A, B} of A and B such that ∅ 6= A ⊆ X,
∅ 6= B ⊆ X, A ∩ B = ∅ and A ∪ B = X. The split metric ξ{A,B} : X × X → {0, 1}
associated with an X-split {A, B} is defined by(
0 if i, j ∈ A or i, j ∈ B,
ξ{A,B} (i, j) =1 otherwise,
for all i, j ∈ X.
The polyhedral split decomposition of polyhedral convex functions is introduced byHirai [5]. By the polyhedral split decomposition, a polyhedral convex function is decomposed into a sum of split functions and the residue, where a split function is a polyhedral
convex function whose value at a point is defined to be the distance between the point
and a hyperplane. Furthermore, the polyhedral split decomposition is applicable to adiscrete function thorough its convex extension.
In [1], Buneman introduced an index of fundamental importance, called the Bunemanindex, to extract a split metric from a metric d, and showed that, if d is a tree metric,d can be represented as the sum of the extracted split metrics. A distance d on X canbe regarded as a discrete function on {χi − χj | i, j ∈ X} by setting d(χi − χj ) = d(i, j).
In [7], the polyhedral split decomposition is applied to the convex extension of d and theresult by Buneman is recovered in a purely geometric way.
In discrete convex analysis, the convex extension of a distance is known to be a positively homogeneous M-convex function. The notion of M-convex functions is introduced
by Murota [8] as a generalization of valuated matroids by Dress and Wenzel [2]. Positively homogeneous M-convex functions form a most fundamental subclass of M-convex
functions.
An interesting fact about the polyhedral split decomposition of a distance is thatit gives a decomposition of a polyhedral M-convex function into a sum of polyhedral
M-convex functions. This is a remarkable fact indeed because, in general, a sum of
M-convex functions is not necessarily M-convex. As the polyhedral split decomposition
is a geometric notion, we aim at giving a geometric explanation to the reason why
the M-convexity is preserved in this decomposition, in particular, in terms of polyhedral
subdivisions induced by M-convex functions. Those polyhedral subdivisions must consistof M-convex polyhedra.
This paper also deals with quadratic M-convex functions. It is known that there is a
one-to-one correspondence between tree metrics and quadratic M-convex functions [6].
For a quadratic M-convex function, a positively homogeneous M-convex function canbe defined at each point of its domain. We show that such a positively homogeneous
M-convex function is representable as the sum of a tree metric and a linear function;
namely, a quadratic M-convex function is split-decomposable at every point, where a
discrete function is said to be split-decomposable if its convex extension is decomposed
into a sum of split functions and a linear function by the polyhedral split decomposition.
Moreover, this fact indicates that a quadratic M-convex function induces a lattice dicing,or equivalently, a zonotope which fills the space facet-to-facet by its translations. As awell-known result on lattice dicings, there is a routine for constructing a quadratic function that induces a lattice dicing [3, 4]. Inspired by this, we propose another canonicalform of a quadratic M-convex function. The form is written as a positive combinationof rank one forms.
This paper is organized as follows. Section 2 briefly describes the polyhedral anddiscrete split decompositions on the basis of [5]. In Section 3, we introduce basic terminology in discrete convex analysis and apply the polyhedral split decomposition to theconvex extension of a distance according to [7]. We give in subsection 3.4 a geometric2explanation for the M-convexity in the decomposition. In Section 4, we apply the polyhedral split decomposition to a quadratic M-convex function and discuss the induced
lattice dicing.

2

Polyhedral and discrete split decomposition

This section describes the polyhedral split decomposition of polyhedral convex functions and the discrete split decomposition of discrete functions on the basis of [5]. The
discrete split decomposition of a discrete function is nothing but the polyhedral split
decomposition of the convex extension of the discrete function.

2.1

Preliminaries

Let R, R+ , and R++ be the set of real numbers, nonnegative real numbers, and positive
real numbers, respectively. We denote by Rn the n dimensional Euclidean space withthe standard inner product h·, ·i. Let 0 and 1 be the all-zero and all-one vectors in Rn ,respectively.
For x, y ∈ Rn , let [x, y] denote the closed line segment between x and y. We refer
to an (n − 1) dimensional affine subspace of Rn as a hyperplane. In particular, for(a, r) ∈ Rn × R, we define a hyperplane Ha,r = {x ∈ Rn | ha, xi = r}, closed half spaces− = {x ∈ Rn | ha, xi ≤ r} and H + = {x ∈ Rn | ha, xi ≥ r}.
Ha,ra,rFor a set S ⊆ Rn , we denote by cone S the conical hull of S, i.e.,()
Xcone S =λt t | T ⊆ S : a finite set, λ = (λt ) ∈ RT+ .
t∈T

The indicator function of a set S ⊆ Rn is the function δS : Rn → R ∪ {+∞} definedby δS (x) = 1 if x ∈ S and δS (x) = 0 otherwise.
For a function f : Rn → R ∪ {+∞}, the effective domain of f , denoted by dom f , isthe set defined by dom f = {x ∈ Rn | f (x) < +∞}, and the epigraph of f , denoted by
epi f , is the set given by epi f = {(x, β) ∈ Rn × R | β ≥ f (x)}.
A polyhedral complex C is a finite collection of polyhedra such that(1) if P ∈ C, all the faces of P are also in C, and(2) the nonempty intersection P ∩ Q of two polyhedra P, Q ∈ C is a face of P and Q.
S
The underlying set of C is the set |C| = P ∈C P . A polyhedral subdivision of a polyhedron
P is a polyhedral complex C with |C| = P .
A convex function f is said to be polyhedral if its epigraph epi f is a polyhedron. Let
f be a polyhedral convex function. By defining, for each proper face F of epi f , a set
F 0 of points in dom f as F 0 = {x ∈ dom f | (x, f (x)) ∈ F }, we obtain a collection ofsubsets of dom f . One can easily see that each set F 0 in this collection is a polyhedron,that is, the collection is a polyhedral subdivision of dom f , which we denote by T (f ).
The following is a well-known fact.
Lemma 2.1. For a polyhedral convex function f , the polyhedral subdivision T (f ) is
given byT (f ) = {F ⊆ Rn | F = argmin(f − hp, ·i) for some p ∈ Rn }.

3

For two polyhedral subdivisions C1 and C2 , the common refinement C1 ∧ C2 is definedby C1 ∧ C2 = {F ∩ G | F ∈ C1 , G ∈ C2 , F ∩ G 6= ∅}. Note that C1 ∧ C2 is a polyhedral
subdivision of |C1 | ∩ |C2 |. In particular, for a finite set of hyperplanes H, we define thepolyhedral subdivision A(H) of Rn as^
A(H) ={H, H + , H − }.
H∈HThat is, A(H) is the partition of Rn by hyperplanes in H.
The polyhedral subdivision by the sum of two polyhedral convex functions amounts
to the common refinement of the two polyhedral subdivisions associated with the given
polyhedral convex functions.
Lemma 2.2. For two polyhedral convex functions f, g with dom f ∩ dom g 6= ∅, we have
T (f + g) = T (f ) ∧ T (g).

2.2

Polyhedral split decomposition

For a hyperplane Ha,r , the split function lHa,r : Rn → R associated with Ha,r is defined
to be the function such that the value lHa,r (x) of each point x in Rn is kak times the
distance between the point x and the hyperplane Ha,r , i.e., lHa,r is given bylHa,r (x) = |ha, xi − r| (x ∈ Rn ).
For a polyhedral convex function f : Rn → R and a hyperplane Ha,r , we define thequotient cHa,r (f ) of f by lHa,r as
cHa,r (f ) = sup{t ∈ R+ | f − tlHa,r is convex}.
Let (a, r) and (a0 , r0 ) be vectors in Rn × R such that (a, r) = k(a0 , r0 ) for some k ∈ Rwith k 6= 0. Since, for t ∈ R+ , f − tlHa,r is convex if and only if f − |k|tlHa0 ,r0 is convex,
we have cHa,r (f ) = |k|cHa0 ,r0 (f ). Hence, cH (f )lH is independent of the equation of a
hyperplane H. From now on, unless otherwise stated, a hyperplane H is assumed to be
represented as H = Ha,r for a normal vector a with kak = 1, and so lH (x) amounts tothe distance between x and H.
We define the set of hyperplanes H(f ) as
H(f ) = {H : hyperplane | 0 < cH (f ) < +∞}.
The basic idea for the polyhedral split decomposition of a polyhedral convex function f
is to subtract split functions associated with hyperplanes in H(f ) from f successively.
In fact, if the effective domain of f is full-dimensional, this idea directly applies to f
thanks to the following fact.
Lemma 2.3 ([5, Lemma 2.5]). Let f : Rn → R ∪ {+∞} be a polyhedral convex function
with dim dom f = n. Suppose that H, H 0 ∈ H(f ) and t ∈ [0, cH (f )]. Then, we have(cH 0 (f ) − t if H = H 0
cH 0 (f − tlH ) =cH 0 (f )otherwise.

4

If dom f is not full-dimensional, there exist infinitely many hyperplanes having thesame intersection with dom f . For this, and only for this, dom f is assumed to be
full-dimensional.
Theorem 2.4 ([5, Theorem 2.2]). A polyhedral convex function f : Rn → R ∪ {+∞}
with dim dom f = n is uniquely decomposable asXf=cH (f )lH + f 0 ,(2.1)
H∈H(f )

where f 0 : Rn → R ∪ {+∞} is a polyhedral convex function with cH 0 (f 0 ) ∈ {0, +∞} forany hyperplane H 0 .
Obviously, we have T (αlH ) = {H, H + , H − } for any α ∈ R++ . Hence, by Lemma 2.2,
the decomposition (2.1) produces a subdivision as in (2.2) below.
Lemma 2.5. For a polyhedral convex function f : Rn → R, the polyhedral subdivision
T (f ) is represented as
T (f ) = A(H(f )) ∧ T (f 0 ).
(2.2)

2.3

Discrete split decomposition

In this paper, a discrete function means a function defined on a finite set of points in
Rn . Let K be a finite set of points in Rn . If K contains the origin 0, we assume thatf (0) = 0.
For a discrete function f : K → R, the homogeneous convex closure of f is defined
by


X

X
f (x) = inf
λy f (y) |λy y = x, λy ≥ 0 (y ∈ K) + δcone K (x) (x ∈ Rn ). (2.3)


y∈K

y∈K

Since K is a finite set, f is a polyhedral convex function with dom f = cone K.
Furthermore, by definition, f is positively homogeneous, i.e., f (αx) = αf (x) holds forα ≥ 0 and x ∈ Rn .
For a function f : Rn → R, we denote the restriction of f to K by f K . A discrete
function g : K → R is said to be convex-extensible if it satisfies g K = g. If f is convexextensible, we call f the homogeneous convex extension of f (the extension of f forshort).
The discrete split decomposition is based on the next lemma; see the proof of Theorem 3.2 in [5].
Lemma 2.6. Let f : K → R be a discrete function on K with dim cone K = n.
For the extension f of f , suppose that H ∈ H(f ) and t ∈ [0, cH (f )]. Then, we havef − tlH = f − tlHK .
Applying the polyhedral split decomposition to the extension of a discrete function,
we obtain the discrete split decomposition.

5

Theorem 2.7 ([5, Theorem 3.2]). Let f : K → R be a discrete function on K with
dim cone K = n. Then, f is uniquely decomposable asX
cH (f )lHK + f 0 ,f=
H∈H(f )

where f 0 : K → R satisfies cH 0 (f 0 ) ∈ {0, +∞} for any linear hyperplane H 0 . Furthermore, we haveXf=cH (f )lH + f 0 .
H∈H(f )

If, in addition, f is convex-extensible, then f 0 is also convex-extensible.
What is worth discussing is a relation between K and H(f ) for a convex-extensible
discrete function f on K. Since f (0) = 0, each hyperplane H ∈ H(f ) is linear, i.e.,
H = Ha,0 for some a ∈ Rn . By the definition of f , an extremal ray of a cone in T (f )is written as αv for some vector v in K and α ∈ R+ . Since T (f ) = A(H(f )) ∧ T (f 0 ),the hyperplanes in H(f ) are limited by the point set K. In fact, H(f ) must satisfy the
K-admissibility defined as follows. A set of linear hyperplanes H is called K-admissible
if H satisfies the following.
(A1) For each H ∈ H, H intersects with the relative interior of cone K.
(A2) For each F ∈ A(H), cone(F ∩ K) = F ∩ cone K.
For simplicity, a hyperplane H is called K-admissible if the set {H} is K-admissible.
We define the set of linear hyperplanes HK as
HK = {H | H : a K-admissible linear hyperplane}.
Since H(f ) is K-admissible, we have H(f ) ⊆ HK for any discrete function f : K → R.
The K-admissibility also relates to the split-decomposability. A function f on a finite
0
set K with
P dim cone K =Kn is said to be split-decomposable if the residue f given by
0
f = f − H∈H(f ) cH (f )lH is equal to the restriction of a linear function.
An addition of the restriction of a linear function to a discrete function f does notchange the quotient for f and hence does not affect the split-decomposability of f ,which follows from the next lemma. Note that the quotient cH (hq, ·i) equals zero for any
hyperplane H.
Lemma 2.8. Let f be a discrete function on K with dim cone K = n. For any factor
α ∈ R++ and any vector q ∈ Rn , we have αf + (hq, ·i)K = αf + hq, ·i
Moreover, according to the following proposition, every split-decomposable function
is constructed from a K-admissible set of hyperplanes. Thus, split-decomposable functions are also determined by K through the K-admissible sets of hyperplanes since theK-admissibility depends on K.
Proposition 2.9 ([5, Proposition 3.5]). Let K be a finite set such that dim cone K = n.
For a subset H of hyperplanes
P HK and positive weights {αH ∈ R++ | H ∈ H} on thehyperplanes in H, let f = H∈H αH lHK . Then the following conditions (a), (b) and (c)are equivalent.
P(a) f = H∈H αH lH + δcone K .
(b) H = H(f ) and αH = cH (f ) for every H ∈ H.
(c) H is K-admissible.

63

M-convex function and polyhedral split decomposition

3.1

M-convex functions

The aim of this subsection is to introduce M-convex functions. For a point x ∈ Rn , wedefine supp+ x = {i | x(i) > 0, i ∈ X} and supp− x = {i | x(i) < 0, i ∈ X}. A function
f : Zn → R ∪ {+∞} with dom f 6= ∅ is said to be M-convex if it satisfies the following
exchange property:(M-EXC[Z]) For x, y ∈ dom f and u ∈ supp+ (x − y), there exists v ∈ supp− (x − y)such thatf (x) + f (y) ≥ f (x − χu + χv ) + f (y + χu − χv ).
The M-convexity is generalized to a polyhedral convex function as follows. A polyhedral convex function f : Rn → R ∪ {+∞} with dom f 6= ∅ is said to be M-convex if itsatisfies the following exchange property:(M-EXC[R]) For x, y ∈ dom f and u ∈ supp+ (x − y), there exist v ∈ supp− (x − y)and a positive number α0 ∈ R++ such thatf (x) + f (y) ≥ f (x − α(χu − χv )) + f (y + α(χu − χv ))for all α ∈ [0, α0 ].
The effective domain of a polyhedral M-convex function is an M-convex polyhedron,
which is defined as follows. A nonempty polyhedron B ⊆ Rn is defined to be an Mconvex polyhedron if it satisfies the following:(B-EXC[R]) For x, y ∈ B and u ∈ supp+ (x − y), there exist v ∈ supp− (x − y) anda positive number α0 ∈ R++ such that x − α(χu − χv ) ∈ B and y + α(χu − χv ) ∈ B
for all α ∈ [0, α0 ].
In fact, a polyhedral convex function f whose subdivision T (f ) consists of M-convex
polyhedra is M-convex, which is a consequence of Lemma 2.1 and the following theorem.
Theorem 3.1 ([10, Theorem 5.2]). For a polyhedral convex function f : Rn → R ∪{+∞} with dom f 6= ∅, the following two conditions (1) and (2) are equivalent.
(1) f is a polyhedral M-convex function.
(2) argmin(f − hp, ·i) is an M-convex polyhedron for every p ∈ Rn with inf(f − hp, ·i) >−∞.
In general, a sum of polyhedral M-convex functions is not necessarily M-convex. Mconvexity of the sum depends on whether the polyhedral subdivision induced by the sum
consists of M-convex polyhedra.

3.2

Homogeneous convex extension of a distance

Let X = {1, 2, . . . , n}, and let Ω be the finite set defined byΩ = {χi − χj | i, j ∈ X}.
A distance d on X can be regarded as a discrete function defined on the set Ω by settingd(χi − χj ) = d(i, j) (i, j ∈ X).
It is important that d is a distance since the convex-extensibility on Ω is guaranteed by
the triangle inequality.
7

Lemma 3.2. A discrete function f : Ω → R with f (0) = 0 is convex-extensible if andonly if f satisfies f (χi − χj ) ≤ f (χi − χk ) + f (χk − χj ) for all i, j, k ∈ X.
In discrete convex analysis, it is known that a positively homogeneous M-convex
function is given by the homogeneous convex extension of a distance on Ω. However,since dim cone Ω = n − 1, we cannot directly apply the polyhedral split decomposition
to the homogeneous convex extension. To cope with this difficulty, we extend Ω to
Ω1 = Ω∪{1, −1}, and define d(1) = d(−1) = 0. Then, cone Ω1 = Rn . The homogeneousconvex extension of d on Ω1 is given, for each x in Rn , by


P

X
i,j∈X λij (χi − χj ) + λ1 1 + λ−1 (−1) = x,.
d(x) = inf
λij d(χi − χj )
λij ≥ 0 (i, j ∈ X), λ1 ≥ 0, λ−1 ≥ 0i,j∈XPFor any point x ∈ Rn , x is represented as x = x0 + λ1 with ni=1 x0 (i) = 0. In fact,
since d(1) = d(−1) = 0, we have d(x) = d(x0 ), which allows us to identify the extensionof d on Ω with that on Ω1 .
Figure 1 (c) illustrates the homogeneous convex extension on Ω of a metric d on
X = {i, j, k}. Since a point in Ω is on a linear hyperplane as in Figure 1 (a), we canproject {(χi − χj , d(i, j)) | i, j ∈ X} to a 3-dimensional space as shown in Figure 1 (b).

Figure 1: The homogeneous convex extension on Ω of a metric d on X = {i, j, k}.

3.3

Discrete split decomposition of a distance

To apply the the polyhedral split decomposition, we need the set HΩ1 of Ω1 -admissible
hyperplanes. For an X-split {A, B}, we denote by H{A,B} the hyperplane Ha{A,B} ,0 with

|A| |B|
χA
χB
a{A,B} =−.
|A| + |B| |A| |B|
For the simplicity of the quotients for d, we use a{A,B} though ka{A,B} k =6 1.
Proposition 3.3 ([7, Proposition 9.3]). The set of Ω1 -admissible hyperplanes is givenbyHΩ1 = {H{A,B} | {A, B} : an X-split} ∪ {H1,0 }.
Furthermore, for each H{A,B} , the quotient cH{A,B} (d) for a split function lH{A,B} isgiven by cH{A,B} (d) = max{0, c̃H{A,B} (d)}, where c̃H{A,B} is represented as
1d(i, k) + d(l, j) − d(i, j) − d(l, k),c̃H{A,B} (d) =min.
2 i,j∈A, k,l∈B d(i, l) + d(k, j) − d(i, j) − d(k, l)8

If, in particular, d is a metric, we have c̃H{A,B} (d) = bd{A,B} , where bd{A,B} is called theBuneman index defined by
bd{A,B} =1min{d(i, k) + d(j, l) − d(i, j) − d(k, l)} .
2 i,j∈A, k,l∈B

Theorem 3.4 ([7, Theorem 9.6]). Let d : X × X → R be a distance. Then d can be
decomposed asX1d=cH{A,B} (d)lHΩ{A,B}+ d0 ,(3.1){A,B}∈Σ(d)where Σ(d) = {{A, B} | {A, B} : an X-split with cH{A,B} (d) > 0} and d0 : X × X → R
is a distance with cH{A,B} (d0 ) = 0 for any X-split {A, B}. Furthermore, we haved=X

cH{A,B} (d) lH{A,B} + d0 .

(3.2)

{A,B}∈Σ(d)The Ω1 -admissibility of a set of hyperplanes can be translated to the compatibilityof X-splits. Two X-splits {A, B} and {C, D} are called compatible if at least one of thesets A ∩ C, A ∩ D, B ∩ C and B ∩ D is the empty set. A collection of X-splits is called
pairwise compatible if any two X-splits in the collection are compatible. For a subset H
of HΩ1 , we denoteΣH = {{A, B} | {A, B} : an X-split with H{A,B} ∈ H}.
Proposition 3.5 ([7, Proposition 9.8]). A set of hyperplanes H ⊆ HΩ1 is Ω1 -admissible
if and only if ΣH is pairwise compatible.
Furthermore, the decomposition (3.1) can be interpreted as a decomposition of dinto a sum of split metrics and some distance d0 . It is easily seen that, for a split
function lH{A,B} , we have lH{A,B} (χi − χj ) = 1 if |{i, j} ∩ A| = 1 and lH{A,B} (χi − χj ) = 0
1
otherwise. Hence, lHΩ{A,B}
can be identified with the split metric ξ{A,B} . Since H{A,B} is1Ω1 -admissible, the extension of lHΩ{A,B}
coincides with lH{A,B} by Proposition 2.9.

Proposition 3.6. For an X-split {A, B}, the split function lH{A,B} is the homogeneousconvex extension of the split metric ξ{A,B} with respect to {A, B}.
It is known that a metric d is a tree metric if and only if d is represented as a sumof split metrics for pairwise compatible X-splits.
Proposition 3.7 ([7, Proposition 9.7]). A metric d is a tree metric if and only if theextension of d is decomposed asX
d=cH{A,B} (d)lH{A,B} .
{A,B}∈Σ(d)By Proposition 3.7, a split-decomposable function f on Ω1 (with f (1) = f (−1) = 0)
corresponds to a sum of a tree metric and a linear function.
Figure 2 illustrates the polyhedral split decomposition of a metric on X with |X| = 3.
It is known that every 3-point metric can be represented as a sum of split metrics, i.e.,d0 = 0 in the decomposition (3.1).
9

Figure 2: The polyhedral split decomposition of a metric on X = {i, j, k}.

3.4

M-convexity of split functions

As in Proposition 3.6, the split function lH{A,B} is the homogeneous convex extensionof the split metric ξ{A,B} , which immediately implies that lH{A,B} is a positively homogeneous M-convex function (if lH{A,B} is restricted on the hyperplane H1,0 ). Then, weare led to the following statement that reveals a remarkable phenomenon for M-convex
functions. Recall that, in general, the sum of M-convex functions is not necessarily
M-convex.
Theorem 3.8. The polyhedral split decomposition of a positively homogeneous M-convex
function as in (3.2) is a decomposition of a polyhedral M-convex function into a sum ofpolyhedral M-convex functions.
The rest of this subsection is devoted to unraveling why the M-convexity is preservedin the polyhedral split decomposition of the extension of a distance. Since the polyhedral
split decomposition is a geometric notion, we explain it especially in terms of geometry.
To this end, we study the polyhedral subdivision induced by split functions since, byTheorem 3.1 and Lemma 2.1, the M-convexity of d is equivalent to the M-convexity of
all cones in T (d).
Consider that we add a split function lH{A,B} to the extension d0 of d0 in (3.1). Since
the polyhedral split decomposition is designed on the basis of Lemma 2.6, lH{A,B} + d0
1
coincides with the extension of lHΩ{A,B}+ d0 , that is,1
lH{A,B} + d0 = lHΩ{A,B}+ d0 .

(3.3)

Since the right-hand side of (3.3) is the extension of a discrete function on Ω1 , theequality requires thatcone(F ∩ Ω) = F ∩ cone Ω for each cone F ∈ T (lH{A,B} + d0 ).

(3.4)

By interpreting the decomposition (3.2) as successive additions of split functions to d0 ,such a property must hold at each of the additions. Since each addition of a split+−
function produces a common refinement of T (lH{A,B} ) = {H{A,B} , H{A,B}, H{A,B}} andthe present polyhedral subdivision, a cone appearing in the addition has a form as+−
H{A,B} ∩F , H{A,B}∩F , or H{A,B}∩F for a cone F . As d0 is M-convex, (the intersections
with cone Ω of) cones in T (d0 ) is M-convex. Hence, according to the interpretation above,
the following observation points out that the preservation of M-convexity in the additionsof split functions is due to a property as in (3.4).
Proposition 3.9. Let F be an M-convex cone, and let {A, B} be an X-split. Then thefollowing (1), (2) and (3) hold.
10

(1) cone((H{A,B} ∩ F ) ∩ Ω) = (H{A,B} ∩ F ) ∩ cone Ω if and only if (H{A,B} ∩ F ) ∩ cone Ωis an M-convex cone.
+++(2) cone((H{A,B}∩ F ) ∩ Ω) = (H{A,B}∩ F ) ∩ cone Ω if and only if (H{A,B}∩ F ) ∩ cone Ωis an M-convex cone.
−−−(3) cone((H{A,B}∩ F ) ∩ Ω) = (H{A,B}∩ F ) ∩ cone Ω if and only if (H{A,B}∩ F ) ∩ cone Ωis an M-convex cone.

Proof. In this proof, we use the fact that a cone is M-convex if and only if every ray ofthe cone has the direction χi − χj for some i, j ∈ X.
We show (1). The only-if part is obvious since the set (H{A,B} ∩ F ) ∩ Ω consists ofvectors χi − χj for i, j ∈ X. By the characterization of M-convex cones, (H{A,B} ∩ F ) ∩cone Ω is M-convex.
Next, we show the if part. Clearly, cone((H{A,B} ∩ F ) ∩ Ω) ⊆ (H{A,B} ∩ F ) ∩ cone Ω.
Then, we show the reverse inclusion. We need to consider only the rays of (H{A,B} ∩F ) ∩ cone Ω. Since (H{A,B} ∩ F ) ∩ cone Ω is M-convex, its ray has the direction χi − χjfor i, j ∈ X. Obviously, χi − χj ∈ Ω. Hence, χi − χj ∈ (H{A,B} ∩ F ) ∩ Ω, and thuscone((H{A,B} ∩ F ) ∩ Ω) = (H{A,B} ∩ F ) ∩ cone Ω.
The assertions (2) and (3) are shown similarly.

4

Quadratic M-convex functions and lattice dicings

In this section, we apply the polyhedral split decomposition to a quadratic M-convex
function. Then, quadratic M-convex function turns out to be a function that is splitdecomposable around each point in its domain. Furthermore, this result indicates that
there is a lattice dicing or, equivalently, a zonotope which fills the space facet-to-facet
by its translation copies [3, 4]. Inspired by a result for lattice dicings, we obtain anothercanonical representation of quadratic M-convex functions.
We start with the property of M-convex functions as described in the next theorem;
see also [9, Theorem 6.61].
Theorem 4.1 ([10, Theorem 4.15]). For an M-convex function f : Zn → R and x ∈dom f , define γf,x (u, v) = f (x + χu − χv ) − f (x) (u, v ∈ X). Then γf,x is a distance.
For each x ∈ dom f , we regard γf,x as a discrete function on Ω1 by setting
γf,x (χi − χj ) = γf,x (i, j) (i, j ∈ X),

γf,x (1) = γf,x (−1) = 0.

Then, by Lemma 3.2 and Theorem 4.1, γf,x is convex-extensible on Ω1 . In addition, thediscrete split decomposition is applicable to γf,x .
We are particularly interested in the case that f is a quadratic M-convex function
on Zn ∩ cone Ω, i.e., f can be represented as f (x) = 12 x> Ax for all x ∈ Zn ∩ cone Ωwith some coefficient matrix A. The interest is because a quadratic M-convex function
is available from a tree metric, i.e., a split-decomposable function on Ω1 . For a distanced : X × X → R+ , a matrix D = (dij ) is defined by dij = d(i, j) for all i, j ∈ X andcalled the distance matrix of d.

11

Theorem 4.2 ([6, Theorem 3.1]). A quadratic form f (x) defined on Zn ∩ cone Ω isM-convex if and only if there exists a tree metric d : X × X → R+ such that1f (x) = − x> Dx (x ∈ Zn ∩ cone Ω),2where D is the distance matrix of d.
Let f be a quadratic M-convex function on Zn ∩ cone Ω. Then, by Theorem 4.2,
f is represented as f (x) = − 12 x> Dx with the distance matrix D of a tree metric d.
Moreover, γf,x for f and x ∈ Zn ∩ cone Ω is given by
γf,x (u, v) = f (x + χu − χv ) − f (x)11= − (x + χu − χv )> D(x + χu − χv ) + x> Dx
2
2
1 >
1
>
>
>
= −x Dχu + x Dχv − χu Dχu + χv Dχu + χ>
Dχv
2
2 v
= h−x> D, χu − χv i + d(u, v) (u, v ∈ X).
Therefore, γf,x can be regarded as a discrete function on Ω1 as follows:
γf,x (·) = d(·) + (h−x> D, ·i)Ω1 .
By Lemma 2.8, we have γf,x = d + h−x> D, ·i. Since cHA,B (γf,x ) for H{A,B} depends only on d, the quotient cHA,B (γf,x ) coincides with cHA,B (d) = max{0, bd{A,B} }.
Furthermore, since d is a tree metric, we have the following by Proposition 3.7.
Theorem 4.3. For a quadratic M-convex function f on Zn ∩ cone Ω and any pointx ∈ Zn ∩ cone Ω, the function γf,x (·) is split-decomposable.
As the set H(γf,x ) is independent of a point x, by abuse of notation, we use H(f )for H(γf,x ).
Let x be a point in Zn ∩ cone Ω. Since γf,x is split-decomposable, the polyhedral
subdivision T (γf,x ) induced by γf,x coincides with the polyhedral subdivision A(H(f ))given by the hyperplane arrangement H(f ). Hence, if H(f ) contains n hyperplanes withlinearly independent normal vectors, the point x amounts to the intersection point of
H1,0 and translations of linear hyperplanes in H(f ). Note that x is a point in the latticegenerated by Ω. Hence, by appropriately translating H1,0 too, every point of the latticegenerated by Ω1 appears as the intersection point of translations of linear hyperplanes in
H(f ) ∪ {H1,0 }, which means that there is a lattice dicing, described below, with respect
to the lattice generated by Ω1 .
We here introduce the lattice dicing in Rn . Let D be a finite set {D1 , D2 , . . . , Dm }of families of equispaced parallel hyperplanes in Rn . A lattice dicing formed by D isan arrangement of hyperplanes in the families in D that satisfies both the following two
properties:(D1) Among hyperplanes in the families of D, there are n hyperplanes with linearly
independent normal vectors.
(D2) For each vertex of the arrangement, there is one hyperplane from each family.
By the condition (D2), the vertex set of a lattice dicing forms a lattice. Note that not
every central hyperplane arrangement provides a lattice dicing. For example, we canchoose at most three lines to make a lattice dicing in R2 . Figure 3 (a) is a lattice dicing
12

in R2 , and (b) is not a lattice dicing. Figure 3 (a) also illustrates the subdivision ofcone Ω for X with |X| = 3 induced by a quadratic M-convex function. In addition, it is
known that a central hyperplane arrangement produces a zonotope that is the Minkowski
sum of the normal vectors of the hyperplanes in the arrangement. For a lattice dicing
of a space, by constructing a zonotope around each of the vertices of the lattice dicing,the space is filled with facet-to-facet zonotopes.

Figure 3: (a) a lattice dicing, (b) not a lattice dicing.

We now turn to the relation between lattice dicings and Ω1 -admissible sets of hyperplanes. Let H = {Ha1 ,0 , Ha2 ,0 , . . . , Ham−1 ,0 , Ham ,0 } be an Ω1 -admissible set of hyperplanes where ai = a{Ai ,Bi } for each i = 1, . . . , m − 1 and am = 1. For each Hai ,0 ∈ H,
let Di be the set of equispaced parallel hyperplanes Hai ,k for each k ∈ Z. Suppose that
H contains n hyperplanes with linearly independent normal vectors. Then, by the argument above, the set D(H) defined to be {D1 , D2 , . . . , Dm } forms a lattice dicing withrespect to the lattice generated by Ω1 .
Corollary 4.4. Let H be a subset of HΩ1 containing H1,0 and n hyperplanes with linearly
independent normal vectors. If H is Ω1 -admissible, then the set D(H) forms a latticedicing with respect to the lattice generated by Ω1 .
Furthermore, as a result on the lattice dicings, it is known that, for a set H of
hyperplanes which provides a lattice dicing, there is a routine for obtaining a quadratic
function that induces the lattice dicing. Inspired by this, we propose another canonicalform for a quadratic M-convex function.
Let f be a quadratic M-convex function, i.e., f (x) = − 12 x> Dx for a tree metric d.
Then, the set H(f ) = {Ha1 ,0 , Ha2 ,0 , . . . , Ham ,0 } of hyperplanes is Ω1 -admissible, whereai = a{Ai ,Bi } for each i = 1, . . . , m. We define a quadratic function g by
g(x) =mX

bd{Ai ,Bi } (hai , xi)2i=1

= x> a1 a2 · · · >
a1
 a> 

 2
am diag[bd{A1 ,B1 } , bd{A2 ,B2 } , . . . , bd{Am ,Bm } ]  .  x,
 .. 
a>mwhere diag[bd{A1 ,B1 } , bd{A2 ,B2 } , . . . , bd{Am ,Bm } ] is a diagonal matrix whose diagonal entries
are bd{A1 ,B1 } , bd{A2 ,B2 } , . . . , bd{Am ,Bm } . Writing g(x) = x> Qx, we have − 12 D 6= Q. Nevertheless, a computation shows that f (x) = g(x) for each point x ∈ Zn ∩ cone Ω.
13

Theorem 4.5. A quadratic form g(x) defined on Zn ∩ cone Ω is M-convex if and only
if there exist a pairwise compatible set of X-splits {{AP1 , B1 }, {A2 , B2 }, . . . , {Am , Bm }}2
and positive numbers λ1 , λ2 , . . . , λm such that g(x) = m
i=1 λi (hai , xi) where ai is thevector given by


χBi
χAi
|Ai | |Bi |−.
ai =|Ai | + |Bi | |Ai | |Bi |Obviously, the term (ha, xi)2 is a rank one form. Hence, g(x) =a positive combination of rank one forms.

Pm2
i=1 λi (hai , xi) is

Acknowledgments
The author is grateful to Satoru Iwata for his useful comments. The author also thanks
Kazuo Mutora for his helpful suggestions. The present work is supported by the 21stCentury COE Program on Information Science and Technology Strategic Core.

References[1] P. Buneman, The recovery of trees from measures of dissimilarity, in: Mathematics
in the Archaeological and Historical Sciences (F. R. Hodson, D. G. Kendall, and P.
Tautu eds.), pp. 387–395, Edinburgh University Press, Edinburgh, 1971.
[2] A. W. M. Dress and W. Wenzel, Valuated matroids, Adv. Math. 93 (1992); 214–250.
[3] R. M. Erdahl and S. S. Ryshkov, On lattice dicing, European J. Combin. 15 (1994);
459–481.
[4] R. M. Erdahl, Zonotopes, dicings, and Voronoi’s conjecture on parallelohedra, European J. Combin. 20 (1999); 527–549.
[5] H. Hirai, A geometric study of the split decomposition, Discrete Comput. Geom. 36(2006); 331–361.
[6] H. Hirai and K. Murota, M-convex functions and tree metrics, Japan J. Indust.
Appl. Math. 21 (2004); 391–403.
[7] S. Koichi, The Buneman index via polyhedral split decomposition, METR 2006-57,
University of Tokyo, 2006.
[8] K. Murota, Convexity and Steinitz’s exchange property, Adv. Math. 124 (1996);
272–311.
[9] K. Murota, Discrete Convex Analysis, SIAM, Philadelphia, PA, 2003.
[10] K. Murota and A. Shioura, Extension of M-convexity and L-convexity to polyhedral
convex functions, Adv. in Appl. Math. 25 (2000); 352–427.

14