数理解析研究所講究録
1068 巻 1998 年 121-133

121

Polytopes of linear programming relaxation
for triangulations
竹内史比古 Fumihiko Takeuchi fumi@is. .u-tokyo.
今井浩
imai@is. .u-tokyo.
Hiroshi Imai
Department of Information Science, University of Tokyo
Hongo, Bunkyo-ku, Tokyo, 113-0033 Japan
今井桂子

Keiko Imai$\mathrm{s}$$\mathrm{a}\mathrm{c}.$$\mathrm{s}$$\mathrm{a}\mathrm{c}.$iPiP

imai@ise.chuo-u.ac.jp

Department of Information and System Engineering, Chuo University
Kasuga, Bunkyo-ku, Tokyo, 112-8851 Japan

Abstract

Universal polytope is the polytope defined as the convex hull of thecharacteristic vectors of all triangul..ations for a given point configuration. The equality system defining this polytope was found, but thesystem of inequalities are not known yet. Larger polytopes, corresponding to linear programming relaxations, have been used in practice. We show that (1) the universal polytope, the polytope of relaxation for (2) clique, (3) cocircuit and (4) chamber conditions havepoint configurations forinclusion relation in this order. Examples
which these polytopes coincide and differ are given. We also
briefly on the difficulty of giving inequalities for the universal polytope.
$0\check{\mathrm{f}}$$\mathrm{d}\mathrm{i}_{\mathrm{S}}^{\mathrm{a}_{\mathrm{C}}}\mathrm{u}\mathrm{S}\mathrm{s}$1Introduction

Triangulation has been an important subject in several areas such as computational geometry and mathematics. One natural approach for handlingall possible triangulations of a given point configuration is to investigate the122polytope made as the convex hull of the characteristic vectors of the triangulations.
This polytope, the universal polytope, was first studied by Billera et al.
with relation to the secondary polytope [2]. Let the configuration be one ofpoints spanning the dimensional space. They showed that this polytope
has dimension
$d$

$n$

larger polytopes, and gave explicit descriptions for the equality conditions of
this polytope [4]. However, the description for the inequality conditions havenot been found yet.
In computational geometry, an important subject is to find the optimal
triangulation according to some cost. For example, the minimum weight
triangulation is among those problems. These problems can be thought ofas optimization problems on the universal polytope. However, neither description of this polytope, by inequalities or by vertices, can be obtained
easily.
Practical approaches taken recently begin the computation by a polytope
larger than the universal polytope [5] [11]. These polytopes are the polytopesof linear programming relaxation of the universal polytope.
In this paper, we will show set inclusions of the universal polytope andseveral polytopes of relaxation (section 2). We also discuss briefiy on the
difficulty of enumerating inequalities for the universal polytope (section 3).

2

Polytopes of relaxationLet
be a point configuration of points spanning the dimensional
space. A set of points
is a simplex if the points are affinely inde$\neq\sigma-1$
pendent. Its dimension is. A simplex of dimension is called an-simplex in short. We represent the set of -simplices by . The polytopes
we consider will be polytopes in.
We define two simplices
to intersect properly if. If not, they intersect improperly.
For a -simplex , we denote its volume by, and the volumeof the whole convex hull by. We name the inequality
inthe volume inequality, and the equality obtained byreplacing the inequality by equality the volume equality. We can also definevolume (in)equality for sets of -simplices by setting the characteristic vector
as the value of the variable.
$A\subset \mathrm{R}^{d}$

$d$

$n$

$\sigma\subset A$

$i$

$d$

$i$

$S_{d}$$\mathrm{I}\mathrm{R}^{S_{d}}$$\sigma,$$\tau$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)\cap \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(\tau)=$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma\cap\tau)$$d$$v_{\sigma}=\mathrm{v}\mathrm{o}\mathrm{l}(\sigma)$$\sigma$$V=\mathrm{v}\mathrm{o}\mathrm{l}(\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(A))$$\sum_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}\leq V$$1\mathrm{R}^{S_{d}}$

$d$

123

A set of -simplices is a triangulation if they (1) intersect properly and(2) satisfy the volume equality. The universal polytope defined by Billera etal. [2] is the convex hull of the characteristic vectors of triangulations:$d$$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{s}\mathrm{a}1=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}${$\chi\tau\in \mathrm{I}\mathrm{R}^{S_{d}}$:$T$

is a triangulation}.

The intersection graph of -simplices is a graph with the -simplices thevertices and edges between pairs of improperly intersecting -simplices. A setof -simplices is a triangulation if and only if (1) it is a (maximal) independent
set of the intersection graph and (2) suffices the volume equality. A maximal
independent set is not necessarily a triangulation. Such example can bemade by Sch\"onhardt’s polytope [10] [12]. The independent set polytope isthe convex hull of the characteristic vectors of independent sets:
$d$

$d$

$d$

$d$

{

$P_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}_{\mathrm{P}}}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}$$x_{I}$:$I$

is an independent set of the intersection graph}.

We immediately have the following lemma.
Lemma 2.1

The volume inequality is valid on the independent \’{s}et polytope,
defined by this becomes the universal polytope:

an.d. the face

$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{s}\mathrm{a}1=P\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{n}\{_{X:\sum v}\sigma\in Sd\sigma\sigma x=V\}$

The -simplices in an independent set only have overlap with volume zero. Thus, any independent set does not have more volume than thewhole convex hull, and satisfies the volume inequality. Since the independent set polytope was the convex hull of the characteristic vectors of the
independent sets, it also satisfies the volume inequality.
Any triangulation is an independent set satisfying the volume equality.
Thus, its characteristic vector belongs to the polytope in the right side. The
universal polytope was the convex hull of such vectors, thus is included in
the right side.
Conversely, take afrom the right side. It is a convex combinationof independent sets. Since the whole combination satisfies the volume equality, all of the independent sets making the combination should satisfy theequality, thus are triangulations. Hence, this combination is a point of theleft side.

Proof.

$d$$\mathrm{p}\mathrm{o}\mathrm{i}\mathrm{n}\grave{\mathrm{t}}$$\square$124

Any triangulation includes at most one element of a clique of the inter. The set of
section graph. It satisfies the clique inequality
points satisfying this condition for all cliques becomes the polytope$\Sigma_{\sigma\in \mathrm{C}\mathrm{l}\mathrm{i}\mathrm{u}}\mathrm{q}\mathrm{e}X_{\sigma}\leq 1$:$P_{\mathrm{C}\mathrm{l}\mathrm{i}\leq 1}\mathrm{q}\mathrm{u}\mathrm{e}=\{x\geq 0$$\forall$(maximal) clique of the intersection graph.

$\sum_{\sigma\in \mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}}x_{\sigma}\leq 1\}$In the proof of theorem 2.3 we will show that the volume inequality is valid
for this polytope. Then its face
$P_{\mathrm{C}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}}1 \mathrm{n}\leq\{x:\sum\sigma\in S_{d}v\sigma X_{\sigma}=V\}$

becomes the feasible points of the linear programming relaxation by cliqueconditions.
We next define polytopes described by chamber conditions [1] [3] [4].
Consider the intersections of the convex hulls of -simplices. A chamber issuch set having positive volume and minimal with respect to inclusion as
point sets. Take a chamber. Any triangulation as exactly one d-simplex
whose convex hull includes that chamber.
$d$$\mathrm{h}$,$\cdot$.

$\bullet$

$+$

$+$

.

$=1$

is called the chamber (in) equality.
The (in)equality
Polytopes defined by these chamber conditions are$\Sigma_{\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}}\mathrm{b}\mathrm{e}\mathrm{r}\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma)^{X_{\sigma}}=(\leq)1$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma\leq 1=$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1=${$x\geq 0:\forall${$x\geq 0:\forall$chamberchamber},$\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\sum_{)\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma}X_{\sigma}\leq 1$$\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{e}\sum_{\mathrm{m}\mathrm{b}\Gamma\subset \mathrm{c}\circ \mathrm{n}\mathrm{v}(\sigma)}x_{\sigma}=1$}.

is the feasible points of the linear programming relaxation by chamber conditions. We have a lemma for these polytopes.
$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$

125
Lemma 2.2
The volume inequality is valid on$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\leq 1$, and it defines the face

$P_{\mathrm{C}} \mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1=P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}}\mathrm{r}\leq 1^{\cap}\{X. :\sum v \sigma\in Sd\sigma\sigma x=V\}$

Proof. The convex hull of each -simplex can be divided into several chambers. We can sum up the volume by chambers:$d$$\sum v_{\sigma}x_{\sigma}=$$\sigma\in S_{d}$vol(chamber)$\sum$

chamber$\sum$$x_{\sigma}$.

$\sigma:\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\subset \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma)$.
This shows that the volume inequality is valid on, and the above rewriting shows thatis included in. Thus the left side is included in thethe volume equality holds onright side.
Conversely, take a point fromsatisfying the volume equality. If
the volume sum cannot
there exists a chamber with
$V$ . Thus all chambers must have
. Hence, it isreacha point of$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\leq 1$$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma\leq 1$$P_{\mathrm{C}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\leq 1$$\sum_{\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}}\mathrm{e}\mathrm{r}\subset \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma)x\sigma<1$$\sum_{\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}}\mathrm{b}\mathrm{e}\mathrm{r}\subset \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)x\sigma=1$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1\cdot\square$

Theorem 2.3$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}\Gamma \mathrm{s}\mathrm{a}}1 \subset P_{\mathrm{C}}1\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\mathrm{n}\{x :\sum_{\sigma\in S_{d}}vx=\sigma\sigma V\}\subset P\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$. Any indepenProof. First, we show
is the convex hull of thedent set satisfies the clique conditions.
. For
characteristic vectors of independent sets, thus is included in
the second inclusion, observe that for any chamber the -simplices including
it are making a clique in the intersection graph.
$P_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{e}\mathrm{n}}\mathrm{P}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}\subset P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1}\subset P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\leq 1$$P_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}_{\mathrm{P}}}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}$$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1}$$d$Thus the clique condition, and we have$\sum_{\sigma\in \mathrm{C}\mathrm{l}\mathrm{i}\mathrm{u}}\mathrm{q}\mathrm{e}X_{\sigma}\leq 1$$\Sigma_{\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}}\mathrm{b}\mathrm{e}\mathrm{r}\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)^{X_{\sigma}}\leq 1$

implies the chamber condition.

$P_{\mathrm{C}}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\subset P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma\leq 1$

126
The volume inequality is valid on
by lemma 2.2. The inclusion above shows that it is valid also on. Thus theandvolume inequality d\‘efines faces of these polytopes and we also have inclusion
relation among them::. By lemmas 2.1, 2.2,
this means$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma\leq 1$$P_{\mathrm{i}\mathrm{n}}\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\iota$$P_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}_{\mathrm{P}}} \mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}\cap\{x :$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1}$\sum_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=V\}\subset P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1}\cap\{x$$\Sigma_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=V\}\subset P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma\leq 1\cap\{x:\Sigma_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=V\}$$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{S}\mathrm{a}1\subset P_{\mathrm{C}}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{x:\Sigma_{\sigma\in S\sigma\sigma}vxd=V\}\subset P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1\square$

The last conditions we consider are the cocircuit conditions by de Loera
et al. [4]. A $(d-1)$ -simplex is in interior if its convex hull is not included in
the boundary of conv $(A)$ . For such interior $(d-1)$ -simplex , the interiorcocircuit condition is$\tau$$\sum$$\sigma\in S_{d}$: ais on one side of$\sum$$x_{\sigma}=$$\tau$$\sigma\in S_{d}$:$\sigma$$x_{\sigma}$

is on the other side of.

$\tau$$\backslash 7=p+\triangle$

Any triangulation satisfies these conditions. The last polytope is defined as$P_{\mathrm{C}\mathrm{o}\mathrm{c}\mathrm{i}_{\Gamma \mathrm{c}}}\mathrm{u}\mathrm{i}\mathrm{t}=\mathrm{a}\mathrm{f}\mathrm{f}(P_{\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{V}}1}\mathrm{e}\Gamma \mathrm{s}\mathrm{a})\cap\{x\geq 0\}$.

De Loera et al. showed the following theorem.
Theorem 2.4 ([4, theorem 1.1])

is the polytope described by the interior cocircuit conditions andone non-homogeneous equality (e.g. the volume equality).
$P_{\mathrm{C}\circ \mathrm{c}\mathrm{i}\mathrm{r}}\mathrm{C}\mathrm{u}\mathrm{i}\mathrm{t}$is the feasible points of the linear programming relaxation by cocircuit conditions.
The following is our second theorem.
$P_{\mathrm{C}\mathrm{O}\mathrm{C}\mathrm{i}_{\Gamma}\mathrm{i}\mathrm{t}}\mathrm{c}\mathrm{u}$Theorem 2.5$P_{\mathrm{C}\mathrm{l}\mathrm{i}\mathrm{u}\mathrm{e}}1 \mathrm{n}\mathrm{q}\leq\{X:.\sum_{\sigma\in Sd}v\sigma x\sigma..V=\}\subset P_{\mathrm{C}\mathrm{O}\mathrm{C}\mathrm{i}_{\Gamma}\mathrm{i}\mathrm{t}}\mathrm{c}\mathrm{u}\subset P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1$

127

Proof. By theorem 2.3, all points insatisfy
for all chambers. The points inalso satisfy.
. Thus.
For the first inclusion, we have to check that any.
satisfies the cocircuit conditions. Suppose it was not satisfied. We should have some interior $(d-1)$ -simplex with
first side of
.
Since
we
took
from
:
side of, and this polytope is included inby theorem 2.3, . satisfies.
the chamber equality for all chambers.
Take a chamber adjacent to on the second side. The set$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{S}\mathrm{a}1$$\sum_{\sigma:\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}}\mathrm{b}\mathrm{e}\mathrm{r}\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)x\sigma=$$1$$\mathrm{a}\mathrm{f}\mathrm{f}(P_{\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{V}}1})\mathrm{e}\Gamma \mathrm{s}\mathrm{a}$$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{m}_{\mathrm{Y}}$$P_{\mathrm{C}\mathrm{O}\mathrm{C}}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}\subset P_{\mathrm{c}\mathrm{h}\mathrm{a}}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$$x\in P_{\mathrm{C}}1\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{x$$\sum\sigma\in s_{d}vx\sigma-\sigma-V\}$$\sum_{\sigma:}$$\tau$$\Sigma_{\sigma:\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}}$$x$$\tau^{X_{\sigma}}$$\tau^{X}\sigma>$$x\in P_{\mathrm{C}}1\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{x$$V\}$$\Sigma_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=$$x$$P_{\mathrm{C}\mathrm{h}}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1$$\cdot$,$\tau${$\sigma$: adjacent to on the first side}: adjacent to on the second side, but intersecting improperly,$\tau$$\cup\{\sigma$$\tau$$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)\}$$\cup${a : crossing$\tau,$$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)$}

is making a clique in the intersection graph. However,$(*)$$\sum$$\sigma$:adjacent to on
the first side$\tau$$>$$\sum$$\sigma$$\sum$$x_{\sigma}+$$\sigma$$\tau$:adjacent to on
the second side$\sigma$: crossing$\sum$$\sigma$on the second side, butintersecting improperly,: adjacent to$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)$,$\sum$$x_{\sigma}+$$\tau$$x_{\sigma}$$\tau$$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}(\sigma)$$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)$$x_{\sigma}+$$\tau$$\sum$$x_{\sigma}+$on the second side, butintersecting improperly,: adjacent to$\sigma$: crossing$x_{\sigma}$$\tau$,$\tau\subset \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}(\sigma)$$= \sum_{\mathrm{V}\sigma:\tau\subset \mathrm{C}\circ \mathrm{n}(\sigma)}x_{\sigma}$$=1$ ,

but since$x$

was satisfying the clique conditions, $(*)\leq 1$ , a contradiction.
$T$$\square$

128

Theorems 2.3, 2.5 lead the main theorem.
Theorem 2.6$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}} \mathrm{r}\mathrm{s}\mathrm{a}1\subset P\mathrm{C}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{X:\sum v\sigma\in Sd\sigma\sigma X=V\}\subset P_{\mathrm{C}\mathrm{O}}\mathrm{c}\mathrm{i}_{\Gamma \mathrm{C}\mathrm{u}}\mathrm{i}\mathrm{t}\subset P_{\mathrm{C}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1$

Remark 2.7, we can get rid of the
For the polytope
volume equality, which has coefficient other than 0/1, adding many 0/1 conditions instead:$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1} \cap\{x :\sum_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=V\}$$P_{\mathrm{C}\mathrm{l}\mathrm{i}\mathrm{u}\mathrm{e}}1 \mathrm{n}\mathrm{q}\leq\{x:\sum vx_{\sigma}=\sigma\in sd\sigma V\}$$=P_{\mathrm{C}1} \mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\mathrm{n}P_{\mathrm{c}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1^{\cap}\{x:\sum_{\sigma\in sd}v_{\sigma}x_{\sigma}=V\}$$=P_{\mathrm{C}\mathrm{l}\mathrm{i}\mathrm{u}}\mathrm{e}1\cap \mathrm{q}\leq \mathrm{c}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}P=1$$=P_{\mathrm{C}}1\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap P\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\geq 1$

Next we will give examples of point configurations to show that theseinclusions can be either equal or proper.
Example 2.8 (polygon)

For the vertices of a polygon de Loera et al. [4, theorem 4.1] showed.

$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{S}}\mathrm{a}1^{\cdot}=P_{\mathrm{c}}1\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{_{X:\sum v}\sigma\in Sd\sigma^{X}\sigma=V\}=P_{\mathrm{C}}\mathrm{O}\mathrm{C}\mathrm{i}_{\Gamma \mathrm{C}}\mathrm{u}\mathrm{i}\mathrm{t}=P_{\mathrm{c}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}=1$

Example 2.9 (regular pentagon with a point in the center)

For this example from [4, example 4.2], the inclusion becomes$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}\mathrm{r}} \mathrm{s}\mathrm{a}11\mathrm{i}\neq^{P_{\mathrm{C}}\cap\{}\subset \mathrm{q}\mathrm{u}\mathrm{e}\leq 1X:\sum v\sigma\in Sd\sigma x\sigma V=\}=P_{\mathrm{C}}\mathrm{o}\mathrm{C}\mathrm{i}_{\Gamma \mathrm{C}}\mathrm{u}\mathrm{i}\mathrm{t}=P_{\mathrm{C}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$

and all the polytopes except$P_{\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{V}\mathrm{e}}1}\mathrm{r}\mathrm{S}\mathrm{a}$has a fractional vertex.

,

129
Example 2.10 (regular 9-gon with a point in the center)show that triangles
In this example, the regions
form a clique in the intersection graph. Thus, the inequality$\langle 138\rangle,$$\mathrm{A},\mathrm{B},\mathrm{C}$$\langle 246\rangle,$$\langle 579\rangle$$X_{\langle 138\rangle}+X\langle 246\rangle+x\langle 579\rangle\leq 1$

must hold onwith$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1}$. On the other hand, there exists a point of$=1/2$ violating that inequality:$P_{\mathrm{C}\mathrm{O}\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{C}\mathrm{u}\mathrm{i}}\mathrm{t}$$X_{\langle 138\rangle}=X_{\langle 246\rangle}=X_{\langle 57}9\rangle$$X_{\langle 138\rangle}=X_{\langle 24}6\rangle=X_{\langle 57}9\rangle=x(038\rangle=X_{\langle 26\rangle}0=x\langle 059\rangle=x\langle 029\rangle=x(035\rangle=X_{\langle 068\rangle}$$=X_{\langle 123\rangle\langle 3}=x24\rangle=X_{\langle 34}5\rangle=X_{\langle 456\rangle\langle 6}=x57\rangle=X_{\langle 67}8\rangle=X_{\langle 78}9\rangle=X_{(189\rangle\langle 2}=x19\rangle$$=1/2$ ,.

$x_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}}\Gamma \mathrm{S}=0$

For this point configuration,$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1} \cap\{x:\sum_{\sigma\in}sdv_{\sigma}x_{\sigma}=V\}_{\neq}^{\subset}P_{\mathrm{C}}\mathrm{o}\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{C}\mathrm{u}\mathrm{i}\mathrm{t}$.

$\frac{\iota}{\prime,c^{3}}.$.

De Loera et . showed that for points in general position,[ , proposition 2.5]. However, for degenerate point configurations,
we cannot guarantee this.

$P_{\mathrm{C}\circ \mathrm{c}\mathrm{i}\mathrm{r}}\mathrm{C}\mathrm{u}\mathrm{i}\mathrm{t}=$$\mathrm{a}.1$$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1$$4$

Example 2.11 (square with a point in the center)

The point. Thushas dimension 2, whilebelongs tofor this point configuration. Further,has dimension 4.

$x_{\langle 012\rangle}=X_{\langle 023\rangle}=X_{(134\rangle}=1,$$P_{\mathrm{C}}\mathrm{o}\mathrm{c}\mathrm{i}\Gamma \mathrm{C}\mathrm{u}\mathrm{i}\mathrm{t}$$P_{\mathrm{C}\mathrm{O}}\mathrm{c}\mathrm{i}_{\Gamma}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}$$P_{\mathrm{C}\circ \mathrm{C}\mathrm{i}_{\Gamma \mathrm{c}\mathrm{u}}}\mathrm{i}\mathrm{t}\neq^{P}\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\subset \mathrm{e}\mathrm{f}=1$$x_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\Gamma \mathrm{s}}=0$$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1$$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1\backslash$130
Remark 2.12
The integers points ofinteger points ofshown in example 2.11
those.

andare the’ thus correspond to the triangulations. However, as
can have extra integer vertices other than

$P_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1} \cap\{x :$P_{\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{V}\mathrm{e}}1}\mathrm{r}\mathrm{S}\mathrm{a}$\sum_{\sigma\in S_{d}}v_{\sigma}x_{\sigma}=V\}$$P_{\mathrm{C}\mathrm{o}\mathrm{c}\mathrm{i}_{\Gamma}\mathrm{i}\mathrm{t}}\mathrm{c}\mathrm{u}$$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1$

Remark 2.13
andhave the same dimension. Thus,also has the same dimension. However, the dimension
can be larger, as shown in example 2.11.

By definition,$P_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{V}\mathrm{e}}\mathrm{r}\mathrm{S}\mathrm{a}1$$P_{\mathrm{C}\mathrm{O}}\mathrm{c}\mathrm{i}_{\Gamma}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}$$P_{\mathrm{C}\mathrm{l}\mathrm{i}\leq}\mathrm{q}\mathrm{u}\mathrm{e}1^{\cap}$$\{x:\sum_{\sigma\in s_{d}\sigma\sigma}vX=V\}$of$P_{\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}=}\mathrm{e}\mathrm{r}1$

From the examples above, we obtain the following theorem.
Theorem 2.14
The polytopes, the inclusion of which we showed in theorem 2.6, can coincide
or differ depending on the given point configuration.

The polytopes we handled correspond to linear relaxations of the universal
polytope. Here we summarize briefly their efficiency in practice.
is the closest to the universal polytope.
To describe this polytope, we have to enumerate all cliques of the intersection
graph. This can be done by the generalized Paull-Unger procedure [8] withimprovements by Tsukiyama et al. [7] [13]. This enumeration can be done inlinear time with respect to the number of cliques, but with a large coefficient.
The investigation of the computational complexity and the number of thecliques for the case of the intersection graph of -simplices remains to be
explored.
is not efficient, because (1) the number of chambers can belarge and (2) there can be new integer points. Giving a base of the chamberconditions is done by Alekseyevskaya [1].
In practice, it has been shown thatis the most efficient [5] [11].
$P_{\mathrm{C}}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\leq 1\cap\{x :\Sigma_{\sigma\in S}dv_{\sigma}x_{\sigma}=V\}$$d$$P_{\mathrm{C}}\mathrm{h}\mathrm{a}\mathrm{m}\mathrm{b}\mathrm{e}\Gamma=1$$P_{\mathrm{C}\mathrm{O}\mathrm{C}\mathrm{i}_{\Gamma}\mathrm{i}\mathrm{t}}\mathrm{c}\mathrm{u}$3Difficulty of enumerating the inequalitiesof$P_{\mathrm{u}\mathrm{n}\mathrm{i}1}\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{S}\mathrm{a}$De Loera et al. gave descriptions for the equality system of the universal
polytope. On the other hand, there are no results for giving descriptions of
the inequalities using geometric information of the point configuration. Even

131partial results for this problem would be useful, because they can result in
defining stricter relaxation polytopes for the universal polytope. However,putationally easy. In
the authors have doubts whether this problem isthis section, we would like to show some examples, which may have relation
with the difficulty of this problem.
$\mathrm{c}\mathrm{o}.\mathrm{m}$,Example 3.1

For the example of regular pentagon with a point in the center (example 2.9),
there is a facet $x_{A}\leq x_{B}+x_{C}$ in the universal polytope. This can be readthen either $x_{B}=1$ or $x_{C}=1$ ” However if there
as a condition
were other points in the left of the triangles $A,$ $B,$ $x_{A}=1,$ $x_{B}=x_{C}=0$ canhappen, and the condition does not hold. Thus, we can say that this facet isrepresenting some “global” information of the point configuration, and thisis one reason we think the problem might be difficult.
$‘(\mathrm{i}\mathrm{f}x_{A}=1$

Ruppert et al. showed that deciding whether a nonconvex polyhedron-complete [9].
can be triangulated or not without adding new vertices is
Triangulability can be judged by computing the intersection of the universal
for -simplices not included in thepolytope and the hyperplanes
polyhedron, which we cannot use. The polyhedron is triangulable if and only
if this intersection is not empty. However, this connection does not immediately imply that giving inequalities is difficult. The triangulability problem
is a decision problem and giving inequalities is an enumeration problem, And
fu.rther, the connection between these problems are not straightforward.
The problem of computing the triangulation with minimum sum of edge
lengths for a given point configuration in the plane is one of the famous
problems in computational geometry. It is not know whether this problem-complete or computable in polynomial time [6]. This problem canisbe solved as an optimization problem on the universal polytope. Even if
the universal polytope has many facets, if we can generate (appropriate)them as cutting
inequalities of the universal polytope efficiently, we canplanes, and compute this problem quickly.
$\mathrm{N}\mathrm{P}$$”’ r_{\sigma}=0$$d$$\sigma$$\mathrm{N}\mathrm{P}$.se$\mathrm{u}$132

Acknowledgments
The authors would like to thank Tomomi Matsui, Yasuko Matsui, Kazuo
Murota and Akihisa Tamura for enlightening comments.

References[1] TATIANA V. ALEKSEYEVSKAYA, Combinatorial bases in systems of
simplices and chambers, Disc. Math., 157 (1996), 15-37.
[2] LOUIS J. BILLERA, PAUL FILLIMAN, AND BERND STURMFELS,
structions and complexity of secondary polytopes, Advances in Math.,
83 (1990), 155-179.

$C_{on}-$[3] LOUIS J. BILLERA, ISRAEL M. GEL’FAND, AND BERND STURMFELS,
Duality and minors of secondary polyhedra, J. Combinatorial Theory,
Ser.B57 (1993), 258-268.
[4] JES\’Us A. DE LOERA, SERKAN HO\S TEN, FRANCISCO SANTOS, AND
BERND STURMFELS, The polytope of all triangulations of a point configuration, Doc. Math., 1 (1996), 103-119.
[5] CID CARVALHO DE SOUZA AND AMINADAB NUNES, Integer programming models for minimum-weight triangulations, 16th international
symposium on mathematical programming, Lausanne, 1997.
[6] MICHAEL R. GAREY AND DAVID S. JOHNSON, Computers and intractability: A Guide to the theory of $NP$-Completeness, W. H. Freeman,
New York, 1979.

[7] E. L. LAWLER, J. K. LENSTRA, AND A. H. G. RINNOOY KAN,
Generating all maximal independent sets: $NP$-Hardness and polynomialtime algorithms, SIAM J. Comput., 9 (1980), 558-565.

[8] M. C. PAULL AND S. H. UNGER, Minimizing the number of states inincompletely specified sequential switching functions, IRE Trans. Electronic Computers, 1959, 356-367.
[9] JIM RUPPERT AND RAIMUND SEIDEL, On the difficulty of triangulating
three-dimensional nonconvex polyhedra, Disc. Comp. Geom., 7 (1992),

227-253.

133
Uber die Zerlegung von Dreieckspolyedern in[10] E. SCH\"ONHARDT,
Tetraeder, Math. Ann., 98 (1928), 309-312.

[11] AKIRA TAJIMA, this volume.
[12] FUMIHIKO TAKEUCHI AND HIROSHI IMAI, Enumerating triangulations
for products of two simplices and for arbitrary configurations of points,
in Proc. Computing and combinatorics: 3rd annual international conference, Lecture Notes in Computer Science 1276, Springer-Verlag, Berlin,

470-481.
[13] SHUJI TSUKIYAMA, MIKIO IDE, HIROMU ARIYOSHI, AND ISAO SH1RAKAWA, A new algorithm for generating all the maximal independent
sets, SIAM J. Comput., 6 (1977), 505-517.