Search
Close this search box.

Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications

Abstract

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in \(\mathbb{R}^3\). Our implementation is complete in the sense that it does not assume general position, namely, it can handle degenerate input, and produces exact results. We also present applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in \(\mathbb{R}^3\). The algorithms use a dual representation of convex polyhedra, and their implementation is mainly based on the Arrangement package of CGAL, the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with a naive approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra. Our method is significantly faster; in some cases it is fifty times faster than the convex-hull approach. The results of experimentation with a broad family of convex polyhedra are reported. The relevant programs, source code, data sets, and documentation are available at collision_detection

Minkowski sum of 2 orthogonal dioctagonal pyramids

Primal

Dual

Dual Unfolded

Movie & Links

  • Dan Halperin and Efi Fogel
    Video: Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications
    In Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), 382-383, Piza, 2005 [mp4 14MB] [link][bibtex]
  • Dan Halperin and Efi Fogel
    Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra with Applications
    Computer Aided Design, 39(11): 929–940, 2007 [link][bibtex]
    In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (Alenex), pages 3–15, Miami, Florida, January 2006 [pdf][bibtex]

Contacts

Efi Fogel
Dan Halperin
@inproceedings{fh-eecmc-06,
  author       = {Efi Fogel and Dan Halperin},
  title        = {Exact and efficient construction of {M}inkowski sums of convex polyhedra with applications},
  booktitle    = {Proceedings of the 8th Workshop on Algorithm Engineering and Experiments ({ALENEX})},
  pages        = {3--15},
  year         = {2006},
  doi          = {10.1137/1.9781611972863.1}
}
@article{fh-eecms-06,
  author = {Efi Fogel and Dan Halperin},
  title = {Exact and efficient construction of {M}inkowski sums of convex polyhedra with applications},
  journal = {Computer Aided Design},
  volume = {39},
  number = {11},
  year = {2007},
  pages = {929--940},
  doi = {10.1016/j.cad.2007.05.017},
  publisher = {Butterworth-Heinemann},
  address = {Newton, MA, USA},
}
@inproceedings{fh-emscp_05,
  author    = {Efi Fogel and Dan Halperin},
  title     = {Video: Exact {M}inkowski Sums of Convex Polyhedra},
  booktitle = {Proceedings of the 21st ACM Symposium on Computational Geometry ({SoCG})},
  Pages     = {382--383},
  site      = {Piza},
  year      = {2005},
  doi       = {10.1145/1064092.1064157}
}

Yair Oz - Webcreator

Contact

Skip to content