Representing polyhedra by few polynomial inequalities

dc.contributor.advisorGrötschel, Martinen
dc.contributor.authorBosse, Hartwig W.en
dc.contributor.grantorTechnische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaftenen
dc.date.accepted2005-05-02
dc.date.accessioned2015-11-20T16:43:23Z
dc.date.available2006-01-23T12:00:00Z
dc.date.issued2006-01-23
dc.date.submitted2006-01-23
dc.description.abstractDiese 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.de
dc.description.abstractThis 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.en
dc.identifier.uriurn:nbn:de:kobv:83-opus-12033
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/1580
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-1283
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherKombinatorikde
dc.subject.otherKonvexe Geometriede
dc.subject.otherPolyederde
dc.subject.otherPolynomede
dc.subject.otherSemi-algebraische Geometriede
dc.subject.otherCombinatoricsen
dc.subject.otherConvex geometryen
dc.subject.otherPolyhedraen
dc.subject.otherPolynomialsen
dc.subject.otherSemi-algebraic geometryen
dc.titleRepresenting polyhedra by few polynomial inequalitiesen
dc.title.translatedBeschreibung von Polyedern mittels weniger Polynomungleichungende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfree*
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.identifier.opus31203
tub.identifier.opus41190
tub.publisher.universityorinstitutionTechnische Universität Berlinen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Dokument_40.pdf
Size:
1.58 MB
Format:
Adobe Portable Document Format
Collections