POLYNOMIAL TIME ALGORITHMS FOR MAXIMIZING THE
INTERSECTION VOLUME OF POLYTOPES

Komei Fukuda∗ and Takeaki Uno†
Dedicated to Masakazu Kojima on the occasion of his 60th birthday.
Abstract: Suppose that we have several polytopes in Rd and we can translate them without rotation.
Here we consider the intersection maximization problem, which asks the positions of the polytopes which
maximizes the volume of their intersection. In this paper, we address this problem, and show that the
problem can be solved in oracle polynomial time by an ellipsoid method, exploiting two important facts.
Namely, the objective function is a continuous piecewise-polynomial function and its dth root is concave. We
further study the structure of the problem in depth for the two dimensional case, and propose an algorithm
which solves it in O(n4 ) time for two non-convex polygons, where n is the total number of vertices.
Key words: polytope, volume, elipsoid method, polynomial time, algorithm arrangement, face lattice
Mathematics Subject Classification: 52B05, 65K05

1 Introduction
Let A and B be two polygons in the Euclidean plane where the position of A is fixed andthe polytope B can be translated freely without rotation. Then, the intersection of A andB changes as the move. Here we consider the intersection maximization problem, that is, tomaximize the volume of the intersection by translation.
Let us consider a simple example of two convex polygons in Figure 1. By shiftinghorizontally the triangle from left to right, the volume of the intersection of the triangle
and the square initially increases as a convex function in the translation variable. Afterthe whole triangle is contained in the square, the volume is constant, and then decreases asa concave function. Thus, the volume of the intersection has both features of convex andconcave functions. One can also see that the function is continuous, but not differentiable.
Consequently, maximization of such functions may not be done in a straightforward manner.
In 1998, de Berg et al. studied this problem and proposed an algorithm running inO(n log n) time for two convex polygons in plane [6], where n is the total number of vertices.
There is also a study of sublinear time randomized algorithm for two convex polygons inplane [1]. However, to the best of our knowledge, neither the non-convex case nor higher
dimensional cases has been studied.
∗ Research supported by the Swiss National Science Foundation Project 200021-105202.
† Research supported by the Swiss National Science Foundation Project PIJS2-109070.

2

K. FUKUDA AND T. UNO

In higher dimensions, the computation of the volume itself is known to be #P-hard [12]when the input is a V-polytope (a convex polytope given as the convex hull of points) or an
H-polytope (a convex polytope given as the solution set to a system of linear inequalities). If
the input two polytopes are identical (i.e. A = B), the maximum volume of their intersection
equals the volume of the input polytope. Thus, the associated problem to decide whether
the maximum intersection volume is a given value is #P-hard for both H-polytopes and Vpolytopes. This fact itself does not make the intersection maximization problem worthless
to investigate, since one can compute the volume of a V-polytope and H-polytope quickly
for considerably complex polytopes in modest (say up to 10) dimensions, see [8]. A natural
question then is whether there exists an oracle polynomial time algorithm for the intersection
maximization problem where the oracle returns the volume of a polytope.
In this paper, we address this problem from the computational point of view. First,
we show that the dth root of the objective function is concave for any finite number of ddimensional convex polytopes. We also show that the hyperplanes spanned by the facets ofthe polytopes define an arrangement where the objective function is a polynomial function ineach of its regions. The problem has this structure even in non-convex cases. It follows that
one can solve the problem in oracle polynomial time by an ellipsoid method where the oracle
returns the volume, which is the objective function of the problem, and its subgradient. By
using these properties, we propose a strongly polynomial time algorithm for the non-convex
case, where the input is given by the union of several polytopes. In the two dimensionalcase of two non-convex polytopes, we propose an enumeration based algorithm which runsin O(n4 ) time and O(n2 ) space.

Figure 1: The volume of the intersection of two polygons
The organization of this paper is as follows. Section 2 sets basic definitions and notations.
We show the concavity of the dth root of the objective function in Section 3, and that it is apiecewise-polynomial function in Section 4. Section 5 describes an ellipsoid method runningin oracle polynomial time. In Section 6, we explore the structure of the problem in the twodimensional case, and present an algorithm running in O(n4 ) time for the non-convex case.

2 Preliminaries
We begin with the definitions related to polytopes. See textbooks, such as [14] to see moredetails.
We denote the d-dimensional Euclidean space by Rd . A convex body A is a convex
compact set with nonempty interior, i.e., A is closed, bounded, and the affine hull of A is
Rd , and for any points x and y in A, the line segment connecting x and y is included in
A. A convex polytope is the intersection of a finite number of closed halfspaces. A convex
polytope is simply called a polytope. A polytope in Rd is called full dimensional if its affine

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

3

hull is Rd , and c-dimensional if the dimension of its affine hull is c. If a polytope is full
dimensional, it is a convex body. A c-dimensional polytope is called a c-polytope.
For c ∈ Rd , b ∈ R, a linear inequality cT x ≤ b is said to be valid for a polytope P if it
is satisfied by all points x in P . A face of a polytope P is a set of form {x ∈ P | cT x = b}
for some valid inequality cT x ≤ b for P . The dimension of a face is the dimension of its
affine hull. A face of dimension c is called a c-face. The 0-faces of P are the vertices of P ,and the (d − 1)-faces of P are the facets of P . The empty set is a unique (−1)-face andP a unique d-face. The set of all faces of P ordered by inclusion is the face lattice of P ,whose least element is the empty set and whose largest element is P . For a facet F of P ,the hyperplane spanned by F is called the affine hyperplane of F , and denoted by H(F ).
We denote by H + (F ) the closed halfspace defined by H(F ) containing P , and by H − (F )the other closed halfspace defined by H(F ). The vertex-facet incidence of P is the bipartite
graph G(P ) = (V1 , V2 , E) where V1 is the set of vertices, V2 the set of facets and (v, F ) ∈ E(v ∈ V1 and F ∈ V2 are adjacent in G) if and only if v ∈ F . The following property is basic,see e.g. [14].
Property 2.1 The face lattices of polytopes P1 and P2 are isomorphic if and only if there is
an isomorphism between G(P1 ) and G(P2 ) preserving the given bipartitions (i.e. the vertices
in V1 (P1 ) are mapped to those in V1 (P2 )).
A d-simplex is a d-polytope with exactly d + 1 vertices. In particular, a d-simplex isoften called simplex, simply. A triangulation ∆ of a d-polytope is a set of d-simplices andtheir faces such that their union is P and the intersection of any two members of ∆ is theircommon face.
For a convex body P in Rd , we denote its d-dimensional volume by vol (P ). For a vector
h in Rd , P +h is the convex body obtained by translating P by h, i.e., P +h = {x+h|x ∈ P }.
Whenever there is no confusion, for simplicity, we call a face of P + h a face of P , insteadof correctly saying “a translated face of P .” For a sequence P of polytopes P1 , . . . , Pk , theirintersection forms a polytope. We call the polytope the intersection polytope, and denote itby ∩(P), i.e., ∩(P) = ∩ki=1 Pi . For a (long) vector‡ h = (h2 , . . . , hk ) ∈ Rd×(k−1) , we denote∩({P1 , P2 + h2 , . . . , Pk + hk }) by ∩(P + h). For a given set of polytopes P = {P1 , . . . , Pk }in Rd , the intersection maximization problem is to maximize vol (∩(P + h)) subject to h ∈Rd×(k−1) . We call the objective function of the problem the volume function. For simplicity,
we may denote vol (∩(P + h)) by vol (h).
Hereafter, unless otherwise specified, P denotes the set of k polytopes P1 , . . . , Pk in Rd ,and h = (h2 , . . . , hk ) ∈ Rd×(k−1) . Without loss of generality, we assume no two input
polytopes Pi and Pj have the faces whose affine hulls can be the same by translation, thus
F 6= F 0 for any face F of Pi and any face F 0 of Pj , as we may translate their initial positions.
We denote by F(P) the set of all facets of all polytopes in P. By the assumption above,
every facet in F(P) is a facet of a unique polytope Pi . Here we present some properties of
the intersection of the polytopes.
Property 2.2 Any c-face of ∩(P + h) with c < d is included in at least one facet of F(P).
For a face f of Pi and h = (h2 , h3 , . . . , hk ) ∈ Rd×(k−1) , we define f + h by f + hi if i ≥ 2
and f otherwise. For a set of facets F = {F1 , . . . , Fm } ⊆ F(P), we define ∩(F + h) by∩({F1 + h, . . . , Fm + h}). For an intersection polytope P = ∩(P + h) and a face f of P , wedefine the topological representation of f , denoted by T (f ), by the set of facets F in F(P)such that F + h includes f . The following properties immediately follow from the definition.
‡ It might be more natural to call h ∈ Rd×(k−1) a matrix but we regard this as a d × (k − 1) dimensional
vector.

4

K. FUKUDA AND T. UNO

Figure 2: Affine hyperplanes of facets, and functional representation of vertex

Property 2.3 Let ∩(P + h) be any intersection polytope. Then the following statements
hold.
(1) No two distinct faces of ∩(P + h) have the same topological representation.
(2) For any faces f and f 0 of ∩(P + h), f ⊆ f 0 if and only if T (f 0 ) ⊆ T (f ).
For an intersection polytope ∩(P + h), we define its topological vertex set by the set of
topological representations of all vertices in ∩(P + h).
For any vertex v of ∩(P + h), the position of v is given by the intersection of the facets
in T (v), i.e., {v} = ∩(T (v) + h). Thus, v is represented as a unique solution to the linear
equation system induced by H(F1 + h), . . . , H(Fm + h), where T (v) = {F1 , . . . , Fm }. Bysolving the system without assigning values to h, we obtain a function in h. We call thisfunction the functional representation of a vertex v. For any vertex of any intersection
polytope ∩(P + h), its functional representation is a linear function in h.
Example 2.4 In Figure 2, the affine hyperplanes of facets F1 and F2 are H(F1 ) = {(x, y)|x+2y = 5}, and H(F2 ) = {(x, y)|3x + 2y = 10}, respectively. The topological representationof vertex v is {F1 , F2 }, and the topological representation of vertex u is {F1 , F3 , F4 }. The
functional representation of v is the solution to the linear system;x + 2y = 5,
3(x − hx ) + 2(y − hy ) = 10.
³
Thus, (x, y) =5+3hx +2hy 5−3hx −2hy
,
2
4

´
.

For a given vector h ∈ Rd×(k−1) , a facet F in F(P) is irredundant if F +h contains a facetof ∩(P + h). A facet is irredundant for some h, and not so for some other h, thus the facelattice of the intersection polytope changes depending on the position of h. The following
lemma, however, shows that the face lattice is uniquely determined by the topological vertex
set.

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

5

Lemma 2.5 Two intersection polytopes having the same topological vertex set T have thesame (isomorphic) face lattice.
Proof. Suppose that ∩(P + h) and ∩(P + h0 ) have the topological vertex set equal to T . We
will show that the sets of irredundant facets are the same for h and h0 . This implies that
two intersection polytopes have the isomorphic vertex-facet incidence, thus the topologicalvertex sets of two intersection polytopes are the same. Then, by Property 2.1, we may
conclude that the face lattices are isomorphic.
Let F be the union of all topological representations in T . Let F ∈ F be a redundant
facet. Since it is redundant, there is an irredundant facet F 0 in F such that {T ∈ T |F ∈ T }is properly contained in {T ∈ T |F 0 ∈ T }. This in fact shows that one can detect all irredundant facets in F by looking only at T . This completes the proof.

3 Convexity on the Intersection Volume of Polytopes
Our first result is the following theorem.
Theorem 3.1 For any two convex bodies A and B in Rd , the function (vol (∩({A, B +h})))1/d is concave in h over the region of nonempty intersection, Ω = {h ∈ Rd | ∩ ({A, B +h}) 6= ∅}.
Notice that the region Ω of nonempty intersection is convex. To see this, we look at
different representations as follows:Ω = {h ∈ Rd | ∩ ({A, B + h}) 6= ∅}= {h ∈ Rd |x = y + h for some x ∈ A and y ∈ B}
= {h ∈ Rd |h = x − y for some x ∈ A and y ∈ B}
= A + (−B) = A − B.
The last line says the region of nonempty intersection is simply the Minkowski sum of A andthe negative copy of B. The third equation above shows that Ω is the orthogonal projection ofa convex body in the space of x, y and h onto the h space. In general, when there are k convex
bodies P1 , . . ., Pk , the corresponding region Ω = {h | ∩ ({P1 , P2 + h2 , . . . , Pk + hk }) 6= ∅} iseasily seen to be an orthogonal projection of a convex body and thus convex.
The special case d = 2 of Theorem 3.1 is proved by [6]. Our proof is a natural extensionof their proof for d = 2. In particular, we use the Brunn-Minkowski theorem below. Let us
denote by H(z, d) the hyperplane in Rd given by xd = z.
Theorem 3.2 (Brunn-Minkowski, see [4]) Let P be any convex body in Rd . Then, thefunction (vol (∩({P, H(z, d)})))1/(d−1) is concave in z over the region Ω = {z ∈ Rd | ∩({P, H(z, d)}) 6= ∅}.
Proof (of Theorem 3.1). Let h, h0 ∈ Rd be any vectors such that both ∩({A, B + h}) and∩({A, B + h0 }) are non-empty. It suffices to show that the function is concave over the line
segment connecting h and h0 . Let
Ā = {(x1 , . . . , xd , λ) | 0 ≤ λ ≤ 1, (x1 , . . . , xd ) ∈ A},
B̄ = {(x1 , . . . , xd , λ) | 0 ≤ λ ≤ 1, (x1 , . . . , xd ) ∈ B + (λh + (1 − λ)h0 ))}.

6

K. FUKUDA AND T. UNO

Figure 3: Polytopes Ā, B̄, and P̄

Since both sets are convex, P̄ = Ā ∩ B̄ is also convex, see Figure 3. Consequently, theintersection of H(λ, d + 1) and P̄ is
H(λ, d + 1) ∩ P̄ = {(x1 , . . . , xd , λ) | (x1 , . . . , xd ) ∈ A, (x1 , . . . , xd ) ∈ B + (λh + (1 − λ)h0 )}= {(x1 , . . . , xd , λ) | (x1 , . . . , xd ) ∈ A ∩ (B + (λh + (1 − λ)h0 ))}.
Thus, the intersection is a lifted copy of ∩({A, B + (λh + (1 − λ)h0 )}). The theorem thenfollows directly from the Brunn-Minkowski Theorem.
The theorem above can be easily extended to the intersection of several convex bodies.
Theorem 3.3 For any set P of k convex bodies P1 , . . . , Pk in Rd , the function vol (∩({P1 ,P2 + h2 , . . . , Pk + hk })))1/d is concave in h = (h2 , . . . , hm ) over Ω = {h | ∩ ({P1 , P2 +h2 , . . . , Pk + hk }) 6= ∅}.
It follows from Theorem 3.1 that any locally maximum solution of the intersection maximization problem is a global maximum solution. This also implies that the volume functionis unimodal. Moreover, it is semistrictly quasiconcave. A function f (x) is called semistrictly
quasiconcave [3] if f (y) < f (λx + (1 − λ)y) holds for any x and y with f (x) > f (y), and0 < λ < 1. Since the dth power of any non-negative concave function satisfies this condition,
the volume function is also a semistrictly quasiconcave function.
Corollary 3.4 For any set P of k convex bodies in Rd , vol (∩(P + h)) is semistrictly quasiconcave in h over Ω = {h | ∩ (P + h) 6= ∅}.

4 Decomposing the Domain into Equivalence Regions
In this section, we will explore the structure of the volume function in depth, and show that it
is a continuous piecewise-polynomial function. In particular, we introduce a decompositionof the region Ω of nonempty intersection (defined in Section 3) into full dimensional convex
polytopes (called pieces) in such a way that the volume function is a polynomial function in

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

7

the translation vector h within each of the pieces. This result will be used when we present
efficient algorithms for the intersection maximization problem in the following sections.
First, we show that the volume function is continuous.
Lemma 4.1 For any sequence P of polytopes P1 , . . . , Pk , vol (∩(P + h)) is continuous in h.
Proof. Let h = (h2 , . . . , hk ) and x = (x2 , . . . , xk ) be arbitrary vectors in Rd×(k−1) , andVi , i = 2, . . . , k be the volume of the polytope obtained by projecting Pi to the hyperplane
normal to xi . Then, we can
P see that for any ² > 0, the difference between vol (h) andvol (h + ²x) is bounded by²Vi ||xi ||. Hence, vol (h) − vol (h + ²x) converges to zero when
² → 0. Therefore vol (h) is continuous.
Note that the volume function is continuous but not differentiable, as we can see in
Figure 1; When the half of the triangle is included in the square, the derivative of thevolume function changes from positive to negative without visiting zero.
Next we investigate the form of the volume function. For this, it is useful to review how
the volume of a polytope can be computed.
There are several methods to compute the volume of a d-polytope P ⊆ Rd . Here we use
the following simple recursive method, proposed by Cohen and Hickey [9]. The method is
to compute a triangulation of P , and compute the sum of the volume of the simplices in thetriangulation. The volume of a d-simplex S with vertices v0 , ..., vd is given by
vol (S) =|det(v1 − v0 , v2 − v0 , . . . , vd − v0 )|,d!

where det(v1 − v0 , v2 − v0 , . . . , vd − v0 ) is the determinant of the matrix composed of column
vectors v1 − v0 , . . . , vd − v0 .
To obtain a triangulation of P , we triangulate faces recursively. Namely, we choose any
vertex v of P , and triangulate every facet of P not containing v recursively. Then thecollection of convex hulls of v and resulting simplices in the triangulations of the chosen
facets is a triangulation of P .
For an intersection polytope ∩(P + h), we consider the expression of the volume with theuse of the functional representations of vertices instead of their positions, given as the sum of
the volumes of d-simplices in a triangulation. We denote this function by Vh : R(k−1)×d → R
and call it a volume function with respect to h. Note that this function is a polynomial of
degree at most d.
For two vectors h and h0 , Vh (h0 ) may not be equal to vol (h0 ). The following theorem
characterizes the case when they are equal. This is extremely important for the design of
our algorithms.
Theorem 4.2 For two vectors h and h0 , Vh (h0 ) = vol (h0 ) if the topological vertex sets of∩(P + h) and ∩(P + h0 ) are equal.
To verify the theorem, we first observe the following fact.
Lemma 4.3 The Cohen-Hickey algorithm behaves identically for all intersection polytopes
having the same topological vertex set.
Proof. This comes from that the Cohen-Hickey algorithm looks at only the structure of theface lattice. Thus, by Lemma 2.5, the algorithm behaves identically for the polytopes withthe same topological vertex set.

8

K. FUKUDA AND T. UNO

Figure 4: Arrangement of the hyperplanes induced by the facets of A and B

Proof (of Theorem 4.2). By Lemma 4.3, the volume function with respect to h, obtainedby the Cohen-Hickey algorithm is equivalent to that of h0 . This completes the proof.
Now we can see that the volume functions of two intersection polytopes are identical
if their topological vertex sets are the same. Thus, Rd×(k−1) is decomposed into maximal
regions in which the topological vertex sets are identical. We call such a region an equivalence
region. See a two dimensional example in Figure 4.
Lemma 4.4 A set F of facets in F(P) is the topological representation of a vertex v of∩(P + h) if and only if the following conditions hold;(a) ∩(F + h) is a point,(b) ∩(F + h) is contained in ∩(P + h), and(c) no facet F in F(P) \ F satisfies v ∈ F + h.
Proof. The only-if part of the statement is obvious. Thus we prove the if part. Supposethat F satisfies the conditions (a), (b) and (c). Let {v} = ∩(F + h), and x be any vector in
Rd satisfying x 6= 0. Since ∩(F + h) is a point, there is at least one facet in F such that its
normal vector is not orthogonal to x. Thus, at most one of v + x and v − x can be includedin ∩(P + h). This together with (b) implies that v is a vertex of ∩(P + h). From (c), F isthe topological representation of v.
For any topological representation T (v), we define the feasible region of T (v) by theset of h such that ∩(P + h) has a vertex whose topological representation is T (v). From
Lemma 4.4, the closure of the feasible region R of T (v) is given by the intersection of thehalfspaces Sv (F ) := {h | ∅ 6= ∩(T (v) + h) ⊆ H + (F + h)}, for any F ∈ F(P). Note that the

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES9

set Sv (F ) can be represented as the set of solutions to a system of one linear inequality andlinear equations in h. More explicitly, the equations determine the unique point specified in
the condition (a) of Lemma 4.4, while the inequality represents the condition (b) expressing
the vertex being on the feasible side of each facet F . The condition (c) does not appear
in the representation of the closure of the feasible region. The boundary of Sv (F ) is theaffine subspace {h | ∅ 6= ∩(T (v) + h) ⊆ H(F + h)}. We call this subspace the boundary
subspace induced by a facet F and a topological representation T (v). When this subspace
is a hyperplane, we call it the boundary hyperplane. Any facet of the feasible region R is
contained in a boundary subspace. Consequently the feasible region is the set of relativeinterior points of a polyhedron.
Lemma 4.5 Let Q be the equivalence region in which the topological vertex set of the intersection polytope is T . Then, Q is the intersection of the feasible regions of the topologicalrepresentations of vertices in T , thus is the relative interior of a polyhedron in Rd×(k−1) .
Since the volume function is continuous, we have the following lemma.
Lemma 4.6 The volume function Vh with respect to h of an equivalence region R represents
the volume function in the closure of R.
In the following, we will show that the equivalence regions can be decomposed intosome regions of a hyperplane arrangement. We here introduce a notation. A set F of
facets in F(P) is called an independent facet set if for any h, the intersection of the affine
hyperplanes of F + h over all F ∈ F, that is ∩({H(F + h) | F ∈ F }), is a point, and for anyi, ∩(F ∩ Fi ) = ∅ if and only if F ∩ Fi = ∅. From this definition, we can see the following
lemma.
Lemma 4.7 The topological vertex set of any full dimensional equivalence region is composed only of independent facet sets.
Proof. Let v be a vertex of some intersection polytope such that T (v) is not an independent facet set. Then, there is a vector h0 such that ∩({H(F + h0 ) | F ∈ T (v)}) is not asingle point. Let h00 be any point in S := {h | ∅ 6= ∩(T (v) + h)}. Since v is a vertex,∩(T (v) + h00 ) = {v} holds, and in particular, the normal vectors of T (v) span Rd . It follows
that ∩({H(F + h0 ) | F ∈ T (v)}) = ∅ and consequently ∩(T (v) + h0 ) = ∅. Then, one caneasily see that ∩(T (v) + (1 − λ)h00 + λh0 ) = ∅ for any 0 < λ ≤ 1. This means that nopoint in S has a full-dimensional neighbor in S, and thus S is not full dimensional. Since S
contains the equivalence region of the intersection polytope, the equivalence region cannot
be full dimensional.
For any F ⊆ F(P), we denote by Fi the set of its facets taken from Pi ∈ P.
Lemma 4.8 Let F ⊆ F(P) be an independent facet set. Then, the following statements
hold.
(1) ∩({H(F ) | F ∈ F}) is a point,(2) for each i, Fi = ∅ or ∩(Fi ) is a face of Pi , and(3) the sum of the dimensions of ∩(Fi ) over all i = 1, . . . , k equals (k−1)d where we consider
the dimension of ∩(Fi ) as d when Fi = ∅.

10

K. FUKUDA AND T. UNO

Proof. (1) and (2) are obvious from the definition. If (3) is violated, then the affine hulls of
Fi ’s are dependent, thus for some h, it has no intersection.
A facet of the closure of an equivalence region is given by a facet of the feasible regionof some topological representation. This together with Lemma 4.4 implies the following
lemma.
Lemma 4.9 Let Q be a full dimensional equivalence region. Then, every facet of Q is
included in a boundary hyperplane H(F, F) := {h | ∩ (F + h) ∈ H(F + h)} for some facet
F ∈ F(P) and some independent facet set F.
Let H(P) be the set of all such boundary hyperplanes. Since every boundary hyperplaneof an equivalence region belongs to H(P), we have the following lemma.
Lemma 4.10 The relative interior of any cell of the hyperplane arrangement H(P) is contained in an equivalence region.
We now have the following theorem characterizing the volume function in detail.
Theorem 4.11 For any sequence P of polytopes P1 , . . . , Pk in Rd , the volume function
vol (∩(P + h)) is a continuous semistrictly quasiconcave piecewise-polynomial function ofdegree at most d on {h | ∩ (P + h) 6= ∅}, where “piecewise-polynomial” means that Rd×(k−1)
is decomposed into pieces which are full dimensional polyhedra, and in each piece the function
is a polynomial in h. Moreover, every facet of each piece is contained in some boundary
hyperplane H(F, F).
Proof. We already showed that the volume function is continuous and semistrictly quasiconcave in Lemma 4.1 and Theorem 3.3. In an equivalence region, the volume function isa polynomial function with some absolute operators, which makes the determinants nonnegative. We here prove that one can replace some absolute-value operators by constants,+1’s and −1’s, according to the sign of the value of determinants. Let h and h0 be interior
points of a full dimensional equivalence region, and Vh0 be the polynomial function obtained
from Vh by replacing each absolute operator by a constant +1 or −1. Lemma 4.3 says thatwhen we continuously move h directed to h0 , the topological structure of the triangulation
does not change, and there is no simplex in the triangulation such that its volume touches
0 during the move. It means that the signs of the determinants of the simplices used tocompute Vh0 do not change during the move, thereby Vh0 (h0 ) = Vh0 (h0 ). Lemma 4.9 shows
the correctness of the representation of the facets of the regions.

5 Ellipsoid Method for Higher Dimensions
The ellipsoid method is a fundamental algorithm for solving convex programming problems[5, 11]. For a given point x and a function f having a maximum solution, a hyperplane iscalled separating hyperplane if it separates x from the set of the optimal solutions. For any
concave function, an ellipsoid method computes a point maximizing the function by finding
polynomially many separating hyperplanes [5, 11]. In this section, we show that we cancompute a separating hyperplane for any h, thus the intersection maximization problem canbe solved in oracle polynomial time where oracle is to answer the volume of a polytope andthe gradient of volume function with respect to a given point.

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

11

Figure 5: Triangulations in three equivalence regions

It is known [5] that for any non-differentiable continuous concave function and a point
x, a separating hyperplane is induced by its subgradient at x. Thus, here we present analgorithm to obtain a subgradient of the volume function by computing the gradient of thevolume function with respect to given h.
Computing a subgradient of the dth root of the volume function is not a trivial task. The
derivative of dth root of the volume function with respect to h is possibly not a subgradient at
h when h is on the boundary of a full dimensional equivalence region. See Figure 5. There are
two full dimensional equivalence regions corresponding to the intersection polytopes drawn
above, and their boundary is the vertical line on the center. In both two full dimensional
regions, the triangulation of the intersection polytope is composed of three simplices. On theother hand, on the center line, the triangulation is composed of two simplices. One simplex
is missing on the center. The functional representation of vertex v is the intersection point of
three facets including v. Thus, the functional representation has no solution when we moveto the right-hand region. If we use the functional representation of vertex u instead of that ofv, the sum of the volume of the two simplices is smaller than the volume of the intersection
polytope. Thus, the derivative of the dth root of the volume function with respect to h ispossibly not a subgradient at h when h is on the boundary of a full dimensional equivalence
region.
Suppose that we are given a vector h ∈ Rd×(k−1) and going to compute a subgradient at
h. If h is an interior point of a full dimensional equivalence region, then the volume function
is differentiable at h, thus a subgradient at h can be obtained easily. Otherwise, we perturb hslightly, by adding a vector (²1 , . . . , ²d×(k−1) ) such that each ²i is a positive number smaller
than any positive real number, and ²i >> ²i+1 holds for any i. We denote the result of
the addition by h0 . We can take such ²’s by introducing a lexicographic ordering, i.e., we
represent each real number r by r = a0 ²0 + a1 ²1 + · · · + ad×(k−1) ²d×(k−1) , where ²0 = 1, andconsider that r > q holds for q = b0 ²0 + b1 ²1 + · · · + bd×(k−1) ²d×(k−1) if there is an index jsuch that ai = bi holds for any i < j and ai > bi holds for i = j.
Since each ²i is sufficiently small, h0 is an interior point of a full dimensional region.
From Lemma 4.6, the volume function Vh0 with respect to h0 satisfies that Vh0 (h) = vol (h),thus the derivative of (Vh0 )1/d gives a subgradient at h.

12

K. FUKUDA AND T. UNO

For a convex programming problem over a feasible region Ω (which is a convex body), let
R ∈ R be a number such that there is a ball of radius R containing Ω, and r ∈ R be a number
such that there is a ball of radius r contained in Ω, and fmax be the maximum function valueon Ω, and fmin is the minimum function value. Then, an ellipsoid method finds an ²-optimal
solution by finding O(d2 (log R + log(fmax − fmin ) − log r − log ²)) separation hyperplanes[5]. Here an ²-optimal solution has an objective value f such that fmax − f ≤ ². For theintersection maximization problem, fmax is the optimal value, and fmin is zero.
The ellipsoid method in [5] needs both r and R to solve the optimization problem.
The standard method is an algorithmic version of the Löwner-John theorem, e.g. see [11,Section 4.6] which computes r, R and an affine transformation so that the transformed bodyis sandwiched between balls of radii r and R with R/r = O(d3/2 ) (i.e. log R−log r is of orderlog d), in oracle polynomial time. Here the oracle is a weak separation oracle for the feasible
region Ω. In our setting, the feasible region can be written as an orthogonal projection of ahigher dimensional convex polytope as explained in Section 3. Therefore, a weak separation
oracle is realizable by solving a polynomial-size LP in either case when input polytopes Pi ’s
are H-polytopes or V-polytopes.
Since fmax ≤ Rd , and fmin ≥ 0, both log fmax and log fmin are bounded by a polynomialin the input size. Combining all observations above, we obtain the following theorem.
Theorem 5.1 For the problem of maximizing the volume of the intersection of k polytopes
in d dimension by translation without rotation, one can compute a solution having objective
value no less than the optimal value minus ² by O(d2 (log R+log(fmax −fmin )−log r −log ²))
oracle calls where the oracle is to return the volume and the gradient of the volume function
with respect to a point. In particular, d2 (log R + log(fmax − fmin ) − log r − log ²) is bounded
by a polynomial in the input size.

6 Algorithm for Two Dimensional CaseIn this section, we assume that d = 2 and k = 2. Thus we address the intersection maximization problem of two polytopes in the plane. For the problem, we present an enumeration
based algorithm running in O(n4 ) time with O(n2 ) space for non-convex polytopes with at
most n vertices. In the following, we will show that at most O(n2 ) hyperplanes are irredundant in H(P), and they are classified into O(n) groups in each of which hyperplanes
are parallel. Here a hyperplane is irredundant if it includes a facet of a full dimensional
equivalence region. Note that ∩(P + h) = ∩({P1 , P2 + h}) since k = 2.
Lemma 6.1 For any two polytopes P = {P1 , P2 } of at most n vertices, (a) there are at
most O(n2 ) irredundant hyperplanes in H(P), and (b) these hyperplanes can be classified
into O(n) groups such that any two hyperplanes in a group are parallel.
Proof. Let Q be a full dimensional equivalence region. Then, each facet of the closure of Q
is contained in a facet of the closure of the feasible region of a topological representation Fof a vertex. We denote the closure by R. We note that R is a polyhedron. From Lemmas
4.7 and 4.8, F is composed of two facets, say F1 and F2 . From Lemma 4.9, F1 and F2 satisfy
that(1) both F1 and F2 are facets of P1 , and F1 ∩ F2 is a vertex of P1 ,(2) both F1 and F2 are facets of P2 , and F1 ∩ F2 is a vertex of P2 , or
(3) F1 and F2 are facets of P1 and P2 , respectively.

MAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

13

By Lemma 4.4, R = {h | ∩({F1 + h, F2 + h}) 6= ∅, ∩({F1 + h, F2 + h}) ∈ ∩({P1 , P2 + h})}.
Thus, in case (1), any facet of R is given by an inequality that the vertex F1 ∩ F2 is in
H + (F + h) for a facet F in P2 . Similarly, in case (2), any facet of R is given by an inequalitythat the vertex (F1 ∩ F2 ) + h is in H + (F ) for a facet F in P1 . In case (3), if F1 and F2 + hintersect, then F1 ∩(F2 +h) is always included in ∩({P1 , P2 +h}). Let u1 and u2 be the vertices
of F1 , and v1 and v2 be the vertices of F2 . From the condition of two segments intersecting,one can see that F1 and F2 + h intersect if and only if u1 ∈ H + (F2 + h), u2 ∈ H − (F2 + h)
(or u1 ∈ H − (F2 + h), u2 ∈ H + (F2 + h)), and v1 + h ∈ H + (F1 ), v2 + h ∈ H − (F1 ) (orv1 + h ∈ H − (F1 ), v2 ∈ H + (F1 )).
In all cases, any facet is given by a hyperplane {h | vi + h ∈ H(F1 )}, or a hyperplane{h | ui ∈ H(F2 + h)}. Since the number of pairs of a vertex and a facet is O(n2 ), there areO(n2 ) hyperplanes which induce a facet of full dimensional equivalence regions. Moreover,the hyperplanes given by a facet F of F({P1 , P2 }) are parallel to each other, hence we canclassify the facets into O(n) parallel classes.
Here we denote by H0 (P) the set of hyperplanes described in the above proof, i.e., thehyperplanes given by {h | v ∈ H(F + h)} for a vertex v of P1 and a facet F of P2 , or givenby {h | u + h ∈ H(F )} for a vertex u of P2 and a facet F of P1 .
Suppose that we are given two non-convex polygons P1 and P2 composed of at mostn edges. From the discussion above, we can see that the volume function is no longer
semistrictly quasiconcave, but still a continuous piecewise-polynomial function. Any pieceis a polyhedron given by the union of the regions in the arrangement of the hyperplanes in
H0 (P = {P1 , P2 }). Here we consider the edge of P1 and P2 as facets of them, and define
H0 (P) by the set of hyperplanes including an edge of P1 or P2 . Then, one can see that
Lemma 6.1 also holds for non-convex case.
Thus, in each region of the arrangement, the intersection maximization problem is a nonconvex non-concave quadratic programming problem with two variables. It can be solved
by evaluating the values of the objective function on the vertices, the edges, and the points
satisfying that the gradient is zero. It can be done in linear time in the number of edges of
the region. We note that the sum of the number of edges in each region is O(n4 ), since eachedge is included in just two regions. Enumerating all regions in the arrangement of O(n2 )lines takes O(n4 ) time by a topological sweep method [10].
Suppose that h and h0 are vectors in equivalence regions adjacent to each other via
facets such that there are facets of the regions that the affine hull of their intersection is(d − 1)-dimensional. We can observe that the topological vertex set of ∩(P + h) and that of∩(P + h0 ) differ by at most a constant size. Thus, we obtain the volume function of one byadding the volumes of several triangles to the other. From the fact we obtain the volume
function corresponding to a region by slight “update.”
Let us see the detail of the update. A topological sweep method finds the regions of a
hyperplane arrangement by sweeping the plane by a topological line which intersects eachhyperplane at most once. Thus, keeping all the regions touching the sweeping line, we canget a neighboring region of a newly output region R. It can be done by looking at each edgeof R, and check whether there is a region including the edge in the memory, or not. Thistakes constant time for each edge. Thus, we can get a neighboring region in linear time of
the number of edges of R. The sum of the numbers of edges in the polytopes touching thesweeping line is O(n2 ).
Next we consider the update of the volume function. Suppose that regions R and R0
are adjacent via a hyperplane induced by a vertex v of P1 and an edge e of P2 . Without
loss of generality, the boundary hyperplane given by e and v overlaps no other boundary

14

K. FUKUDA AND T. UNO

hyperplane. Let e1 and e2 be the edges incident to v, u1 and u2 are the intersection pointsof e and e1 , and that of e and e2 , respectively. We denote the volume functions with respect
to R and R0 by V and V 0 . When we translate P2 so that e contains v, there are two cases.
The first case is that H + (e) (or H − (e)) contains both e1 and e2 , and the second case isthat H + (e) contains one of e1 and e2 . In the first case, the difference between V and V 0 is
the volume of the triangle given by v, u1 , and u2 . This can be computed in constant time.
The difference is also the triangle given by v, u1 and u2 in the second case. In any case, thecomputation time for the update is O(1).
Now, we obtain the following result.
Theorem 6.2 The problem of maximizing the volume of the intersection of two non-convex
polygons in the plane can be solved in O(n4 ) time and O(n2 ) space.
When the number of polytopes is a fixed constant k, we can also solve the problem of
non-convex cases in strongly polynomial time. When we are given k non-convex polygons,
the size of H0 (P = {P1 , . . . , Pk }) is O(k 3 n3 ) since any independent facet set is given by twoedges taken from some polygons. The number of regions in a hyperplane arrangement ofO(k 3 n3 ) hyperplanes in R2k−2 is O((k 3 n3 )2k−2 ). The regions are enumerated by a reverse
search algorithm [2] in O((k 3 n3 )L(2k − 2, k 3 n3 )) time for each, where L(2k − 2, k 3 n3 ) is thetime to solve a linear programming problem with 2k − 2 variables and O(k 3 n3 ) inequalities.
In each full dimensional region, we compute the derivative of the volume function, and solve
it to obtain the points in the region with the zero gradient. Since the volume function
is a quadratic function with 2k − 2 variables, we can find a point x where the derivative
vanishes by solving a linear programing problem of 2k−2 variables with O(k 3 n3 ) inequalities,
which takes O(L(2k − 2, k 3 n3 )) time. In total, we can solve the problem in O(L(2k −2, k 3 n3 )(k 3 n3 )2k−2 ) time. Note that since k is fixed, L(2k − 2, k 3 n3 ) is O(n3 ).
Theorem 6.3 One can solve the intersection maximization problem of k non-convex polygons in the plane in O(L(2k − 2, k 3 n3 )(k 3 n3 )2k−2 ) time, where L(2k − 2, k 3 n3 ) is the time
to solve a linear programming problem of 2k − 2 variables with O(k 3 n3 ) inequalities.
In the d-dimensional cases, the size of H0 (P) is bounded by O((kn)(ndk )) = O(kndk+1 )for polytopes with at most n facets, since each hyperplane is given by a combination of
faces taken from polytopes in P, and a facet in F(P). Thus the number of regions in thearrangement is bounded by O((kndk+1 )d ). For each region, we need to solve a polynomial
system with degree at most d. By considering this task as an oracle, we obtain the following
theorem.
Theorem 6.4 One can solve the intersection maximization problem of k non-convex polytopes in Rd by solving polynomial systems of degrees d in a polytope at most O((kndk+1 )d )times.

7 Conclusion
In this paper, we addressed the problem of maximizing the volume of the intersection ofpolytopes. We proved that the dth root of the objective function of the problem is concave inany dimension d, and thus the objective function is continuous and semistrictly quasiconcave.
Using these, we showed that the problem can be solved by an ellipsoid method in oracle
polynomial time, where oracle is to return the volume of a given polytope and its gradient on
the point at which the function is differentiable. Moreover, it was shown that the objectiveMAXIMIZING THE INTERSECTION VOLUME OF POLYTOPES

15

function is a piecewise-polynomial function of degree at most d, and each piece is a polytope.
The piece is decomposed into regions of the arrangements associated with the faces of thepolytopes. For the two dimensional case, we presented an enumeration based algorithm
running in O(n4 ) time for two non-convex polygons with at most n edges.
It is interesting to study the enumeration problem of the equivalent regions in which
the set of vertices of the intersection is equivalent, which enables us to perform an efficient
enumeration based algorithm for solving this problem. We can also consider the problem ofminimizing the union of two polytopes, or the convex hull of two polytopes. We believe thatthese problems have similar structures to the intersection maximization problem, but it is
not clear whether the objective functions have any sort of concavity. We shall leave theseas open problems to be investigated in the future.

Acknowledgment
We thank Masakazu Kojima, Akiko Takeda of Tokyo Institute of Technology, Akiyoshi
Shioura of Tohoku University, and Junya Goto of Tsukuba University for their kind support
in answering various technical questions on convex optimization. The authors would liketo thank anonymous referees for their careful reading of earlier versions of the paper andmany constructive comments. This research is partially supported by Swiss National Science
Foundation and Japan Society for the Promotion of Science.

References[1] H. Ahn, O. Cheong, C. Park, C. Shin and A. Vigneron, Maximizing the overlap of twoplanar convex sets under rigid motions, Symposium on Comput. Geom. 2005, Computational Geometry (2005) 356–363.
[2] D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Appl. Math. 65 (1996)
21–46.
[3] M. Avriel, W.E. Diewert, S. Schaible and I. Zang, Generalized Concavity, Plenum, New
York, 1988.
[4] K. Ball, An elementary introduction to modern convex geometry, in Flavors of Geometry, Math. Sci. Res. Inst. Publ. 31, Cambridge University Press, Cambridge, 1997.
[5] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, Analysis,
Algorithms, and Engineering Applications, MPS-SIAM Series on Optimization, SIAM
and MPS, 2001.
[6] M. de Berg, O. Cheong, O. Devillers, M. J. van Kreveld and M. Teillaud, Computing
the maximum overlap of two convex polygons under translations, Theory of Comput.
Syst. 31 (1998) 613–628.
[7] P. Brass, A lower bound for Lebesgue’s universal cover problem, in Workshop of Discrete
Geometry, Mathematisches Forschungsinstitut Oberwolfach, 2005.
[8] B. Büeler, A. Enge and K. Fukuda, Exact volume computation for convex polytopes:
a practical study, in Polytopes – Combinatorics and Computation, G. Kalai and G. M.
Ziegler (eds.), DMV-Seminar 29, Birkhäuser, 2000, pp. 131–154.

16

K. FUKUDA AND T. UNO[9] J. Cohen and T. Hickey, Two algorithms for determining volumes of convex polyhedra,
J. ACM. 26 (1979) 401–414.
[10] H. Edelsbrunner and L. J. Guibas, Topologically sweeping an arrangement, J. Comput.
System Sci. 38 (1989) 165–194.
[11] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial
Optimization, Springer-Verlag, 1993.
[12] L.G. Khachiyan, Complexity of polytope volume computation, in New Trends in Discrete and Computational Geometry, J. Pach (edi.), Springer-Verlag, Berlin, 1993, pp.
91–101.
[13] G.T. Toussaint, A simple linear algorithm for intersecting convex polygons, The VisualComputer 1 (1985) 118–123.
[14] G.M. Ziegler, Lectures on Polytopes, Springer-Verlag, New York, 1998 (Second revised
printing) .

Manuscript received 22 March 2006
revised 22 May 2006
accepted for publication 2 November 2006

Komei Fukuda
Institute for Operations Research and Institute of Theoretical Computer Science,ETH Zentrum, CH-8092 Zurich, and IMA/ROSO, EPF Lausanne, CH-1015 Lausanne, Switzerland
E-mail address: fukuda@ifor.math.ethz.ch

Takeaki Uno
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
E-mail address: uno@nii.jp