Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Minkowski sums of polytopes : combinatorics and computation
 
doctoral thesis

Minkowski sums of polytopes : combinatorics and computation

Weibel, Christophe  
2007

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.

  • Files
  • Details
  • Metrics
Type
doctoral thesis
DOI
10.5075/epfl-thesis-3883
Author(s)
Weibel, Christophe  
Advisors
Liebling, Thomas M.  
Jury

Günter Ziegler, Komei Fukuda, Peter Gritzmann

Date Issued

2007

Publisher

EPFL

Publisher place

Lausanne

Public defense year

2007-08-17

Thesis number

3883

Total of pages

114

Subjects

Minkowski sums

•

polytopes

•

zonotopes

•

f-vectors

•

perfectly centered

•

Sommes de Minkowski

•

polytopes

•

zonotopes

•

f-vecteurs

•

parfaitement centrés

EPFL units
ROSO  
Faculty
SB  
School
IMA
Doctoral School
EDMA  
Available on Infoscience
June 27, 2007
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/9356
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés