Exact minkowski sums of convex polyhedra

ABSTRACT

We present an exact imp ementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R³. Our implementation is complete in the sense that it does not assume general position, namely, it can handle degenerate input, and produces exact results. Our software also includes applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in R³. 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 naïve approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra.Our method is significantly faster. The video demonstrates the techniques used on simple cases as well as on degenerate cases. The relevant programs, source code, data sets, and documentation are available at http://www.cs.tau.ac.il/~efif/CD Inparticular this site contains a detailed report [3 ]on our algorithms and their implementation including the experimental comparison with the convex-hull approach.

REFERENCES

• 1: The Cgal project homepage. http://www.cgal.org/.
• 2: The GNU MP bignum library. http://www.swox.com/gmp/.
• 3: E. Fogel and D. Halperin. Exact and efficient construction of Minkowski sums of convex polyhedra with applications. Manuscript, Tel Aviv University. http://www.cs.tau.ac.il/~efif/CD/exact mink 3d.pdf 2005.
• 4: E. Fogel, R. Wein, and D. Halperin. Code flexibility and program efficiency by genericity: Improving Cgals arrangements. In Proc. 12th Annu. Euro. Sympos. Alg. volume 3221, pages 664--676. Springer-Verlag, 2004.
• 5: Lutz Kettner, Using generic programming for designing a data structure for polyhedral surfaces, Computational Geometry: Theory and Applications, v.13 n.1, p.65-90, May 1999 [doi>10.1016/S0925-7721(99)00007-3]
• 6: M.C. Lin and D. Manocha. Collision and proximity queries. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, 2nd Edition chapter 35, pages 787--807. CRC, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance