Computational Geometry Seminar

Wednesday, April 26th, 2006, 16:10-18:00

Room 309
Schreiber Building

Exact and Efficient Construction of Minkowski Sums of Convex Polyhedra

Efi Fogel, Tel Aviv University

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in 3D. Our implementation is complete in the sense that it does not assume general position. Namely, it can handle degenerate input, and it produces exact results. 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 the only three other methods that produce exact results we are aware of. One is a simple approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra.
The second is based on Nef polyhedra embedded on the sphere, and the third is an output sensitive approach based on linear programming. Our method is significantly faster.
The talk will cover in depth the linear programming based method above developed by Fukuda and implemented by Weibel.

This is joint work with D. Halperin.