Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra in convex pieces

P. Hachenberger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
96 Downloads (Pure)

Abstract

We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning. The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small amount of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations. The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r 2) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron.
Original languageEnglish
Title of host publicationProceedings of the 15th Annual European Symposium on Algorithms (ESA 2007) 8-10 October 2007, Eilat, Israel
EditorsL. Arge, M. Hoffmann, E. Welzl
Place of PublicationBerlin
PublisherSpringer
Pages669-680
ISBN (Print)978-3-540-75519-7
DOIs
Publication statusPublished - 2007
Eventconference; ESA 2007, Eilat, Israel; 2007-10-08; 2007-10-10 -
Duration: 8 Oct 200710 Oct 2007

Publication series

NameLecture Notes in Computer Science
Volume4698
ISSN (Print)0302-9743

Conference

Conferenceconference; ESA 2007, Eilat, Israel; 2007-10-08; 2007-10-10
Period8/10/0710/10/07
OtherESA 2007, Eilat, Israel

Fingerprint Dive into the research topics of 'Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra in convex pieces'. Together they form a unique fingerprint.

  • Cite this

    Hachenberger, P. (2007). Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra in convex pieces. In L. Arge, M. Hoffmann, & E. Welzl (Eds.), Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007) 8-10 October 2007, Eilat, Israel (pp. 669-680). (Lecture Notes in Computer Science; Vol. 4698). Springer. https://doi.org/10.1007/978-3-540-75520-3_59