Konstruktive Darstellbarkeit und Approximierbarkeit von semi-algebraischen Mengen durch Polynome mit festen Grad
Final Report Abstract
Der Forschungsschwerpunkt lag in der theoretischen Grundlagenforschung bzgl. der konstruktiven Darstellbarkeit von Polyedern und einfachen semi-algebraischen Mengen durch ''wenige'' Polynomungleichungen. Hier wurden die gesteckten Ziele bei weitem erfüllt. Wir konnten eine Konstruktionsvorschrift angeben, die zu jedem einfachen d-dimensionalen Polytop d Polynome bestimmt, die als Ungleichungen das Polytop beschreiben. Die Anzahl der benötigten Polynome ist optimal und verbessert frühere Resultate. Bezüglich beliebigen Polytopen und Polyedern konnten wir dies vorerst nur in Dimension 3 verifizieren. Es ist darüber hinaus auch gelungen, den Fall der einfachen Polytope auf ''generische'' semi-algebraischen Mengen zu verallgemeinern. Hier wird jedoch das so genannte Lemma von Lojasiewicz benutzt, was apriori nur zu einem semi-konstruktiven Verfahren führt. Inwieweit sich die Benutzung dieses Lemmas vermeiden lässt, ist Gegenstand gegenwärtiger Untersuchungen. Die Grade der Polynome in einer minimalen (bzgl. der Anzahl) Darstellung einer semi-algebraischen Menge werden im Allgemeinen sehr hoch sein. Daher waren (sind) wir auch daran interessiert zu verstehen, wie viele Polynome bei vorgegebenem Grad notwendig sind. Eine vollständige Antwort in dem Fall von 2-dimensionalen Polygonen ist Gegenstand einer weiteren Arbeit im Rahmen dieses Forschungsprojektes. Es ist beabsichtigt, die hier gewonnenen algorithmischen/ konstruktiven Resultate in den Teilprojekten TP1 und TP3 anzuwenden. Im Falle der polyedrischen Relaxierungen aus TP1 sind erste Ansätze entwickelt worden, die in naher Zukunft auch erste Resulate liefern werden.
Publications
- (2008): Representing elementary semi-algebraic sets by a few polynomial inequalities: A constructive approach
Averkov, Gennadiy
- Description of polygonal regions by polynomials of bounded degree, Monatsh. Math.
Averkov & Bey
(See online at https://doi.org/10.1007/s00605-010-0224-x) - Notes on the algebra and geometry of polynomial representations, Beiträge Algebra Geom., 50 (2009), no. 1, 271-282
Averkov
- Three-dimensional polyhedra can be described by three polynomial inequalities, Discrete Comput. Geom., 42(2), 2009, 166-186
Averkov & Henk
(See online at https://doi.org/10.1007/s00454-009-9183-1)
