More Web Proxy on the site http://driver.im/

Article

On the hardness of minkowski addition and related operations

Author:

Hans Raj TiwaryAuthors Info & Claims

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

Pages 306 - 309

https://doi.org/10.1145/1247069.1247124

Published: 06 June 2007 Publication History

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]

D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry, 8:295--313, 1992.

Digital Library

[2]

E. Balas. On the convex hull of the union of certain polyhedra. Operations Research Letters, 7:279--283, 1988.

Digital Library

[3]

A. Bemporad, K. Fukuda, and F.D. Torrisi. Convexity recognition of the union of polyhedra. Comput. Geom, 18(3):141--154, 2001.

Digital Library

[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]

M.R. Bussieck and M.E. Lübbecke. The vertex set of a 0/1-polytope is strongly P-enumerable. Comput. Geom, 11(2):103--109, 1998.

Digital Library

[6]

M.E. Dyer, A.M. Frieze, and R. Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1--17, 1991.

Digital Library

[7]

K. Fukuda. From the zonotope construction to the minkowski addition of convex polytopes. J. Symb. Comput., 38(4):1261--1272, 2004.

Digital Library

[8]

K. Fukuda, T.M. Liebling, and C. Lutolf. Extended convex hull. Computational Geometry, 20(1--2):13--23, 2001.

Digital Library

[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]

Gritzmann and Sturmfels. Minkowski addition of polytopes: Computational complexity and applications to grobner bases. SIJDM: SIAM Journal on Discrete Mathematics, 6, 1993.

Digital Library

[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]

L. Khachiyan, E. Boros, K. Borys, K.M. Elbassioni, and V. Gurvich. Generating all vertices of a polyhedron is hard. In SODA, pages 758--765. ACM Press, 2006.

Digital Library

[14]

L.G. Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191--194, 1979.

[15]

J.S. Provan. Efficient enumeration of the vertices of polyhedra associated with network LP's. Math. Program, 63:47--64, 1994.

Digital Library

[16]

G.M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics, No. 152. Springer-Verlag, Berlin, 1995.

Cited By

Keren DSagy GAbboud ABen-David DSchuster ASharfman IDeligiannakis A(2014)Geometric Monitoring of Heterogeneous StreamsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2013.18026:8(1890-1903)Online publication date: Aug-2014
https://doi.org/10.1109/TKDE.2013.180
Tiwary HElbassioni KTeillaud M(2008)On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphismProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377707(192-198)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377707

Index Terms

On the hardness of minkowski addition and related operations
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ^d, we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by ...
On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes

For polytopes P1,P2źźd, we consider the intersection P1źP2, the convex hull of the union CH(P1źP2), and the Minkowski sum P1+P2. For the Minkowski sum, we prove that enumerating the facets of P1+P2 is NP-hard if P1 and P2 are specified by facets, or if ...
Minkowski Decomposition of Associahedra and Related Combinatorics

Realisations of associahedra with linear non-isomorphic normal fans can be obtained by alteration of the right-hand sides of the facet-defining inequalities from a classical permutahedron. These polytopes can be expressed as Minkowski sums and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

June 2007

404 pages

ISBN:9781595937056

DOI:10.1145/1247069

Program Chair:
Jeff Erickson
University of Illinois, Urbana-Champaign, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Keren DSagy GAbboud ABen-David DSchuster ASharfman IDeligiannakis A(2014)Geometric Monitoring of Heterogeneous StreamsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2013.18026:8(1890-1903)Online publication date: Aug-2014
https://doi.org/10.1109/TKDE.2013.180
Tiwary HElbassioni KTeillaud M(2008)On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphismProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377707(192-198)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377707

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents