### Wednesday, May 3rd, 2017 16:10

### Schreiber 309

### Minkowski Sums of Polyhedra with Holes

### Dan Halperin, TAU

### Abstract:

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, 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 polyhedra. 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.