**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Polytope

Summary

In elementary geometry, a polytope is a geometric object with flat sides (faces). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. In this context, "flat sides" means that the sides of a (k + 1)-polytope consist of k-polytopes that may have (k – 1)-polytopes in common.
Some theories further generalize the idea to include such objects as unbounded apeirotopes and tessellations, decompositions or tilings of curved manifolds including spherical polyhedra, and set-theoretic abstract polytopes.
Polytopes of more than three dimensions were first discovered by Ludwig Schläfli before 1853, who called such a figure a polyschem. The German term polytop was coined by the mathematician Reinhol

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (14)

Loading

Loading

Loading

Related courses (1)

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years.

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.

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f- vectors of Minkowski sums of several polytopes.

2007Related people (1)

Related concepts (40)

Related units

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is a polyhedron th

Platonic solid

In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regula

Dual polyhedron

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to

No results

This is a short paper on different proofs for special cases of a conjecture about Minkowski sums of polytopes.

2006Related lectures (1)