Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1283
Main Title: Representing polyhedra by few polynomial inequalities
Translated Title: Beschreibung von Polyedern mittels weniger Polynomungleichungen
Author(s): Bosse, Hartwig W.
Advisor(s): Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Dissertation präsentiert neue Ergebnisse sowohl in der reellen algebraischen Geometrie als auch in der Polyedertheorie. Das Hauptresultat ist der konstruktive Beweis, dass jedes d-dimensionale Polyeder durch höchstens 2d Polynomungleichungen beschreibbar ist. Für die entsprechenden Polynome wird ein Konstruktionsalgorithmus explizit angegeben. Als Folge ergeben sich: Jeder d-dimensionale polyedrische Kegel kann durch 2d-2 Polynomungleichungen beschrieben werden, und jedes beschränkte, d-dimensionale Polytop kann durch 2d-1 Polynomungleichungen beschrieben werden. Für beide Fälle liefert die Arbeit entsprechende Konstruktionsalgorithmen. In jedem der Fälle ist die Anzahl der konstruierten Polynome nah an der untereren Schranke: Um ein d-dimensionales Polyeder darzustellen, das eine Ecke besitzt, werden mindestens d Polynomungleichungen benötigt.
This work presents results in the field of real algebraic geometry as well as in the theory on polyhedra. The main result is that every d-dimensional polyhedron can be described by at most 2d polynomial inequalities and, moreover, an explicit construction for these polynomials is provided. It is also shown that for any d-dimensional pointed polyhedral cone there is a description using (2d-2) polynomial inequalities, and that for bounded polyhedra there is a representation involving 2d-1 polynomial inequalities. A construction for the necessary polynomials is provided for both cases. In each case, the number of polynomials constructed is close to the lower bound: To represent a d-dimensional polyhedron containing a vertex, at least d polynomial inequalities are needed.
URI: urn:nbn:de:kobv:83-opus-12033
http://depositonce.tu-berlin.de/handle/11303/1580
http://dx.doi.org/10.14279/depositonce-1283
Exam Date: 2-May-2005
Issue Date: 23-Jan-2006
Date Available: 23-Jan-2006
DDC Class: 510 Mathematik
Subject(s): Kombinatorik
Konvexe Geometrie
Polyeder
Polynome
Semi-algebraische Geometrie
Combinatorics
Convex geometry
Polyhedra
Polynomials
Semi-algebraic geometry
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_40.pdf1.62 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.