Minkowski sums of polytopes
combinatorics and computation
Weibel, Christophe
Liebling, Thomas M.
Dir.
text
thesis
Doctoral thesis
thesis
EPFL
Lausanne
114 p.
Minkowski sums are a very simple geometrical operation, with applications in many different fields. In particular, Minkowski sums of polytopes have shown to be of interest to both industry and the academic world. This thesis presents a study of these sums, both on combinatorial properties and on computational aspects. In particular, we give an unexpected linear relation between the f-vectors of a Minkowski sum and that of its summands, provided these are relatively in general position. We further establish some bounds on the maximum number of faces of Minkowski sums with relation to the summands, depending on the dimension and the number of summands. We then study a particular family of Minkowski sums, which consists in summing polytopes we call perfectly centered with their own duals. We show that the face lattice of the result can be completely deduced from that of the summands. Finally, we present an algorithm for efficiently computing the vertices of a Minkowski sum of polytopes. We show that the time complexity is linear in terms of the output for fixed size of the input, and that the required memory size is independent of the size of the output. We also review various algorithms computing different faces of the sum, comparing their strong and weak points.
2007 Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2007 ; no 3883
Minkowski sums ; polytopes ; zonotopes ; f-vectors ; perfectly centered
oai:infoscience.epfl.ch:thesis-3883
http://library.epfl.ch/theses/?nr=3883
http://library.epfl.ch/theses/?nr=3883
http://doc.rero.ch/record/11018
20150420163236.0
11018