Representing polyhedra by few polynomial inequalities

Bosse, Hartwig W.

Representing polyhedra by few polynomial inequalities

dc.contributor.advisor	Grötschel, Martin	en
dc.contributor.author	Bosse, Hartwig W.	en
dc.contributor.grantor	Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften	en
dc.date.accepted	2005-05-02
dc.date.accessioned	2015-11-20T16:43:23Z
dc.date.available	2006-01-23T12:00:00Z
dc.date.issued	2006-01-23
dc.date.submitted	2006-01-23
dc.description.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.	de
dc.description.abstract	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.	en
dc.identifier.uri	urn:nbn:de:kobv:83-opus-12033
dc.identifier.uri	https://depositonce.tu-berlin.de/handle/11303/1580
dc.identifier.uri	http://dx.doi.org/10.14279/depositonce-1283
dc.language	English	en
dc.language.iso	en	en
dc.rights.uri	http://rightsstatements.org/vocab/InC/1.0/	en
dc.subject.ddc	510 Mathematik	en
dc.subject.other	Kombinatorik	de
dc.subject.other	Konvexe Geometrie	de
dc.subject.other	Polyeder	de
dc.subject.other	Polynome	de
dc.subject.other	Semi-algebraische Geometrie	de
dc.subject.other	Combinatorics	en
dc.subject.other	Convex geometry	en
dc.subject.other	Polyhedra	en
dc.subject.other	Polynomials	en
dc.subject.other	Semi-algebraic geometry	en
dc.title	Representing polyhedra by few polynomial inequalities	en
dc.title.translated	Beschreibung von Polyedern mittels weniger Polynomungleichungen	de
dc.type	Doctoral Thesis	en
dc.type.version	publishedVersion	en
tub.accessrights.dnb	free	*
tub.affiliation	Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik	de
tub.affiliation.faculty	Fak. 2 Mathematik und Naturwissenschaften	de
tub.affiliation.institute	Inst. Mathematik	de
tub.identifier.opus3	1203
tub.identifier.opus4	1190
tub.publisher.universityorinstitution	Technische Universität Berlin	en

Files

Original bundle

Now showing 1 - 1 of 1

Name:: Dokument_40.pdf
Size:: 1.58 MB
Format:: Adobe Portable Document Format

Download

Collections

Publications