On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

Abstract

Primal

Dual

Dual bottom view
The Minkowski sum \(M_{11,11} = P_{11} \oplus P’_{11}\), where \(P’_{11}\) is \(P_{11}\) rotated \(90^\circ\) about the vertical axis

We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in \(\mathbb{R}^3\). In particular, we prove that the maximum number of facets of the Minkowski sum of two convex polyhedra with \(m_1,m_2,\ldots,m_k\) facets respectively is bounded from above by \(\sum_{1 \leq i < j \leq k} (2m_i – 5)(2m_j – 5) + \sum_{1 \leq i \leq k} m_i + \binom{k}{2}\). Given \(k\) positive integers \(m_1,m_2,\ldots,m_k\), we describe how to construct \(k\) polytopes with corresponding number of facets respectively, such that the number of facets of their Minkowski sum is exactly \(\sum_{1 \leq i < j \leq k} (2m_i – 5)(2m_j – 5) + \sum_{1 \leq i \leq k} m_i + \binom{k}{2}\). When \(k = 2\), for example, the expression above reduces to \(4m_1 m_2 −9m_1 −9m_2 +26\). A few pre-constructed polytopes and an interactive program that visualizes them are available at Mink.

Links

  • Efi Fogel, and Dan Halperin, and Christophe Weibel
    On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra
    Journal of Discrete and Computational Geometry, Springer New York, 42(4): 654–669, 2009 [link][bibtex]
    In Proceedings of the 23rd ACM Symposium on Computational Geometry (SoCG), pages 319–326, Gyeongju, South Korea, 2007 [link][bibtex]
    In Proceedings of the 23rd European Workshop on Computational Geometry (EuroCG), pages 38–41, Graz, 2007 [pdf][bibtex]

Contacts

Dan Halperin
Efi Fogel 
@inproceedings{fhw-emcms-07,
  author       = {Efi Fogel, Dan Halperin, and Christophe Weibel},
  title        = {On the Exact Maximum Complexity of {M}inkowski Sums of Convex Polyhedra},
  booktitle    = {Proceedings of the 23rd European Workshop on Computational Geometry (EuroCG)},
  pages        = {38--41},
  year         = {2007},
  site         = {Graz, Austria}
}

@inproceedings{fhw-emcms-07,
  author       = {Efi Fogel, Dan Halperin, and Christophe Weibel},
  title        = {On the Exact Maximum Complexity of {M}inkowski Sums of Convex Polyhedra},
  year         = {2007},
  booktitle    = {Proceedings of the 23rd annual symposium on Computational geometry ({SoCG})},
  pages        = {319--326},
  location     = {Gyeongju, South Korea},
  doi          = {10.1145/1247069.1247126},
  publisher    = {ACM Press},
  address      = {New York, NY, USA}
}

@article{fhw-emcms-07,
  author       = {Efi Fogel, Dan Halperin, and Christophe Weibel},
  title        = {On the Exact Maximum Complexity of {M}inkowski Sums of Convex Polyhedra},
  journal      = {Discrete and Computational Geometry},
  publisher    = {Springer},
  volume       = {42},
  number       = {4},
  pages        = {654--669},
  year         = {2009},
  doi          = {10.1007/s00454-009-9159-1}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content