Minkowski Sums of Polyhedra with Holes

Dan Halperin, School of Computer Science, Tel-Aviv University

Date and time: 2pm, Friday, December 14, 2018

Place: CUNY Graduate Center, Rm 4419

The Minkowski sum of two sets $P$ and $Q$ in Euclidean space is the result of adding every point (position vector) in $P$ to every point in $Q$. Considering the Minkowski sum of two polyhedra with holes (voids), we show that one can always fill up the holes in one of the summand polyhedra and still get the same Minkowski sum as of the original summands. We present a simple proof of this observation, improving on (our) earlier rather involved proof of a more restricted claim. As we explain, this observation helps in speeding up the computation of Minkwoski sums in practice. We also review additional recent results in computing and using Minkowksi sums.

Joint work with Alon Baram, Efi Fogel, Michael Hemmer, and Sebastian Morr.