Algorithmische Geometrie: Polyedrische und algebraische by Michael Joswig, Thorsten Theobald

By Michael Joswig, Thorsten Theobald

In dem Lehrbuch wird eine mathematisch orientierte Einführung in die algorithmische Geometrie gegeben. Im ersten Teil werden „klassische“ Probleme und Techniken behandelt, die sich auf polyedrische (= linear begrenzte) Objekte beziehen. Hierzu gehören beispielsweise Algorithmen zur Berechnung konvexer Hüllen und die Konstruktion von Voronoi-Diagrammen. Im zweiten Teil werden grundlegende Methoden der algorithmischen algebraischen Geometrie entwickelt und anhand von Anwendungen aus Computergrafik, Kurvenrekonstruktion und Robotik illustriert. Das Buch eignet sich für ein fortgeschrittenes Modul in den derzeit neu konzipierten Bachelor-Studiengängen in Mathematik und Informatik.

Show description

Read Online or Download Algorithmische Geometrie: Polyedrische und algebraische Methoden PDF

Similar german_3 books

Standards für das Gesundheitsmanagement in der Praxis : Konsequenzen des gesetzlichen Präventionsauftrags für Unternehmen und den Arbeits- und Gesundheitsschutz

The articles during this ebook summarize the paintings awarded on the ultimate workshopof the price eu Cooperation within the box of clinical and TechnicalResearch motion on Molecular fabrics and sensible Polymers for AdvancedDevices, which used to be held in June 2000 in Patras, Greece. The collectiongives a great review of the cutting-edge during this box and theprogress made via the coordinated examine initiatives.

Personal im Sozialmanagement: Neueste Entwicklungen in Forschung, Lehre und Praxis

Die Qualität sozialer Einrichtungen und Dienste wird durch ihre Mitarbeiterinnen und Mitarbeiter geprägt; das own ist der Erfolgsfaktor im Sozialmanagement. Auf Einladung der Bundesarbeitsgemeinschaft Sozialmanagement/Sozialwirtschaft präsentierten und diskutierten Wissenschaftler und Praktiker aus Deutschland, Österreich und der Schweiz die neuesten Entwicklungen.

Kampf um Strom. Mythen, Macht und Monopole

Alles im grünen Bereich? Von wegen! Deutschland ist Vize-Exportweltmeister, in Europa übernehmen wir die Schulden der Nachbarländer, und die Bundeskanzlerin gilt als die mächtigste Frau der Welt. Nur die Energiewende will nicht so richtig in Gang kommen. Denn Atomausstieg allein reicht nicht. Und der Umstieg auf erneuerbare Energien ist kompliziert.

Erfolgreich Projekte leiten: Überlegt planen, entscheiden, kommunizieren und realisieren

Der staatlich dipl. Immobilien-Treuhänder Erwin Roth warfare langjährig in leitender place bei IBM beschäftigt und ist seit 1990 als selbständiger Berater und Projektleiter tätig.

Extra info for Algorithmische Geometrie: Polyedrische und algebraische Methoden

Sample text

Zusammen mit dem schwachen Dualitätssatz folgt, dass das duale Problem beschränkt ist sowie die Gleichheit der Optimalwerte. Die Fälle, bei denen eines der Probleme unbeschränkt oder unzulässig ist, verbleiben als Übungsaufgabe. 3 Der Simplex-Algorithmus Der bekannteste Algorithmus zur linearen Programmierung ist der SimplexAlgorithmus (Dantzig, 1947). Dazu betrachten wir ein lineares Programm der Form max { cx : x ∈ P} mit P = P( A, b) = { x ∈ R n : Ax ≤ b} wie zuvor. Wir nehmen zunächst an, dass das Polyeder volldimensional, spitz ist und dass sogar eine Ecke von P bereits bekannt ist („Startecke“).

M−n Durch Übergang zum Dualen ergibt sich dieselbe obere Schranke für die Anzahl der Ecken eines n-Polytops mit m Facetten. 42 nicht in voller Stärke zeigen, statt dessen jedoch einen Beweis für eine obere Schranke wiedergeben, die die richtige Größenordnung für die Anzahl der Facetten zeigt. 44 Ein n-Polytop mit m Ecken besitzt höchstens 2( m als 2n+1 ( n/2 O(m n/2 ). m n/2 ) Facetten und insgesamt nicht mehr ) Seiten. Für festes n haben beide Anzahlen daher die Größenordnung Wir zeigen diese Aussage zunächst für simpliziale Polytope und führen dann den Fall nicht-simplizialer Polytope darauf zurück.

Ausgabe : Eine optimale Ecke v von P (und dualen Vektor y) oder ein Vektor s ∈ R n mit As ≤ 0 und cs > 0 (das heißt, das LP ist unbeschränkt). I ← Indexmenge einer Basis für v Bestimme ein y ∈ (R n )∗ mit yA = c und y i = 0 für alle i ∈ I. 1. 6 aus der Tatsache, dass in einer Ecke mindestens n (linear unabhängige) Ungleichungen mit Gleichheit erfüllt sein müssen. Es werden zunächst alle aktiven Ungleichungen bestimmt, und anschließend kann mittels Gauß-Elimination hieraus eine Basis des Dualraums (R n )∗ ausgerechnet werden.

Download PDF sample

Rated 4.74 of 5 – based on 39 votes