On the hardness of minkowski addition and related operations

ABSTRACT

For polytopes P,Q ⊂ R^d we consider the intersection P ∪ Q; the convex hull of the union CH(P ∪ Q); and the Minkowski sum P+Q. We prove that given rational H-polytopes P₁,P₂,Q it is impossible to verify in polynomial time whether Q=P₁+P₂, unless P=NP. In particular, this shows that there is no output sensitive polynomial algorithm to compute the facets of the Minkowski sum of two arbitrary H-polytopes even if we consider only rational polytopes. Since the convex hull of the union and the intersection of two polytopes relate naturally to the Minkowski sum via the Cayley trick and polarity, similar hardness results follow for these operations as well.

REFERENCES

• 1: David Avis , Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete & Computational Geometry, v.8 n.3, p.295-313, 1992 [doi>10.1007/BF02293050]
• 2: E. Balas. On the convex hull of the union of certain polyhedra. Operations Research Letters, 7:279--283, 1988.
• 3: A. Bemporad, K. Fukuda, and F.D. Torrisi. Convexity recognition of the union of polyhedra. Comput. Geom, 18(3):141--154, 2001.
• 4: D. Bremner, K. Fukuda, and A. Marzetta. Primal -- dual methods for vertex and facet enumeration. Discrete & Computational Geometry, 20(3):333--357, 1998.
• 5: Michael R. Bussieck , Marco E. Lübbecke, The vertex set of a 0/1-polytope is strongly P-enumerable, Computational Geometry: Theory and Applications, v.11 n.2, p.103-109, Oct. 1998 [doi>10.1016/S0925-7721(98)00021-2]
• 6: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 7: K. Fukuda. From the zonotope construction to the minkowski addition of convex polytopes. J. Symb. Comput., 38(4):1261--1272, 2004.
• 8: Komei Fukuda , Thomas M. Liebling , Christine Lütolf, Extended convex hull, Computational Geometry: Theory and Applications, v.20 n.1-2, p.13-23, October 2001 [doi>10.1016/S0925-7721(01)00032-3]
• 9: K. Fukuda and C. Weibel. Computing all faces of the minkowski sum of V-polytopes. In Proceedings of the 17th Canadian Conference on Computational Geometry, 2005.
• 10: Peter Gritzmann , Bernd Sturmfels, Minkowski addition of polytopes: computational complexity and applications to Gro¨bner bases, SIAM Journal on Discrete Mathematics, v.6 n.2, p.246-269, May 1993 [doi>10.1137/0406019]
• 11: B. Grünbaum. Convex Polytopes. Wiley Interscience Publ., London, 1967.
• 12: K. Fukuda and C. Weibel. On f-vectors of minkowski additions of convex polytopes. Technical report, 2005. submitted to DCG.
• 13: Leonid Khachiyan , Endre Boros , Konrad Borys , Khaled Elbassioni , Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.758-765, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109640]
• 14: L.G. Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191--194, 1979.
• 15: J. Scott Provan, Efficient enumeration of the vertices of polyhedra associated with network LP's, Mathematical Programming: Series A and B, v.63 n.1, p.47-64, Jan. 7, 1994 [doi>10.1007/BF01582058]
• 16: G.M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics, No. 152. Springer-Verlag, Berlin, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
coNP-hardness, computational geometry, extended convex hull, minkowski addition, polytope intersection, polytopes, turing reduction