Minkowski sums of polytopes

Christophe Weibel
EPFL, 2007
Thèse EPFL

Résumé

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.

Official source

https://infoscience.epfl.ch/record/109334?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

In this thesis we investigate a number of problems related to 2-level polytopes, in particular regarding their combinatorial structure and extension complexity. 2-level polytopes have been introduced as a generalization of stable set polytopes of perfect graphs, and despite their apparently simple structure, are at the center of many open problems: these include connection with communication complexity and the separation between linear and semidefinite programming. The extension complexity of a polytope P is a measure of the complexity of representing P: it is the smallest size of an extended formulation of P, which in turn is a linear description of a polyhedron that projects down to P. In the first chapter we introduce themain concepts that will be used through the thesis and we motivate our interest in 2-level polytopes. In the second chapter we examine several classes of 2-level polytopes arising in combinatorial settings and we prove a relation between the number of vertices and facets of such polytopes, which is conjectured to hold for all 2-level polytopes. The proofs are obtained through an improved understanding of the combinatorial structure of such polytopes, which in some cases leads to results of independent interest. In the third chapter we study the extension complexity of a restricted class of 2-level polytopes, the stable set polytopes of bipartite graphs, for which we obtain improved lower and upper bounds. In the fourth chapter we study slack matrices of 2-level polytopes, important combinatorial objects related to extension complexity, defining operations on them and giving algorithms for the following recognition problem: given a matrix, determine whether it is a slack matrix of some special class of 2-level polytopes. In the fifth chapter we address the problem of explicitly obtaining small size extended formulations whose existence is guaranteed by communication protocols. In particular we give an output-efficient algorithmto write down extended formulations for the stable set polytope of perfect graphs, making a well known result by Yannakakis constructive, and we extend this to all deterministic protocols. We then conclude the thesis outlining themain open questions that stem from our work.

EPFL

Chargement

, ,

This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods of asynchrony as in the Internet. The measure expresses the ability of processes to reach a consensus decision in a minimal number of rounds of information exchange, as a function of (a) the ability to use authentication and (b) the number of actual process failures, in those rounds, as well as of (c) the total number of failures tolerated and (d) the system configuration. The measure holds for a framework where the different roles of processes are distinguished such that we can directly derive a meaningful bound on the time complexity of implementing robust general services in practical distributed systems. To prove our theorem, we establish certain lower bounds and we give algorithms that match these bounds. The algorithms are all variants of the same generic asynchronous Byzantine consensus algorithm, which is interesting in its own right.

2004

Chargement

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.

2007

Chargement

EPFL