AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

-- Not specified --

-- Not specified --

Saarbrücken

A polytope in R^d is the Convex Hull of a finite number of points in R^d (V-representation). Alternatively, a polytope can be represented as the intersection of a finite number of halfspaces in R^d (H-representation). In this talk I will present hardness results for performing certain operations on polytopes. In particular I will address three operations - computing the Minkowski sum of two H-polytopes, computing the intersection of two V-polytopes and computing the convex hull of union of two H-polytopes. The main result presented in the talk will be that none of these operations can be performed in polynomial time unless P=NP.

Diana Olivier

--email hidden

passcode not visible

logged in users only