Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
In this thesis we consider the problem of converting the halfspace representation of a polytope to its vertex representation - the Vertex Enumeration problem - and various other basic and closely related computational problems about polytopes. The problem of converting the vertex representation to halfspace representation - the Convex Hull problem - is equivalent to vertex enumeration. In chapter 3 we prove that enumerating the vertices of an unbounded H-polyhedron P is NP-hard even if P has only 0=1 vertices. This strengthens a previous result of Khachiyan et. al. [KBB+06]. In chapters 4 to 6 we prove that many other operations on polytopes like computing the Minkowski sum, intersection, projection, etc. are NP-hard for many representations and equivalent to vertex enumeration in many others. In chapter 7 we prove various hardness results about a cone covering problem where one wants to check whether a given set of polyhedral cones cover another given set. We prove that in general this is an NP-complete problem and includes important problems like vertex enumeration and hypergraph transversal as special cases. Finally, in chapter 8 we relate the complexity of vertex enumeration to graph isomorphism by proving that a certain graph isomorphism hard problem is graph isomorphism easy if and only if vertex enumeration is graph isomorphism easy. We also answer a question of Kaibel and Schwartz about the complexity of checking self-duality of a polytope. ; In dieser Arbeit betrachten wir das Problem, die Halbraumdarstellung eines Polytops in seine Eckendarstellung umzuwandeln, - das sogenannte Problem der Eckenaufzählung - sowie viele andere grundlegende und eng verwandte Berechnungsprobleme für Polytope. Das Problem, die Eckendarstellung in die Halbraumdarstellung umzuwandeln - das sogenannte Konvexe-Hüllen Problem - ist äquivalent zum Problem der Eckenaufzählung. In Kapitel 3 zeigen wir, dass Eckenaufzählung für ein unbeschränktes H-Polyeder P selbst dann NP-schwer ist, wenn P nur 0=1-Ecken hat. Das verbessert ein ...