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

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

Best german_3 books

Vergleichsstudie Ar 432

Эксплуатационное руководство самолета“Ar 432”.

Extra info for Algorithmische Geometrie: Polyedrische und algebraische Methoden

Example text

5) Wir unterscheiden nun zwei Fälle: Falls j gerade: Jede (k − 1)-Seite von Pj ist der Durchschnitt einer k-Seite von P mit der Hyperebene Hj , so dass f k−1 ( Pj ) = ∑ F ∈Fk ( P ) χ j ( F) , für 1 ≤ k ≤ n . 5) liefert n ∑ (−1)k−1 ∑ k =1 F ∈Fk ( P ) χ j ( F) = 1 . 6) Falls j ungerade: Jede (k − 1)-Seite von Pj ist der Durchschnitt einer k-Seite von P mit Hj , mit Ausnahme der in Hj enthaltenen Ecke v (( j+1)/2). Daher gilt f 0 ( Pj ) = 1 + f k−1 ( Pj ) = ∑ F ∈F1 ( P ) ∑ F ∈Fk ( P ) χ j ( F) , χ j ( F) , 2 ≤ k ≤ n.

Anderenfalls gilt genau dann a j (v + λs) ≤ b j , wenn λ ≤ (b j − a j v)/( a j s). 3 Der Simplex-Algorithmus 57 Um festzustellen, wann v + λs den Zulässigkeitsbereich P verlässt, betrachten wir alle Ungleichungen simultan und erhalten so die zu zeigende Aussage des Lemmas. 18 gewählte λs maximal ist, wird für λs > 0 im Punkt v + λs s eine Ungleichung aktiv, die vorher nicht aktiv war. 19 Sei j ein Zeilenindex der Matrix A mit λs = (b j − a j v)/( a j s). Dann ist v := v + λs s eine Ecke von P und ( I \ {i }) ∪ { j} die Indexmenge einer Basis für v .

En so orientiert, dass E1+ ∩ · · · ∩ En+ der positive Orthant ist. Die beschriebene affine Transformation lässt sich am bequemsten mittels des Produktes zweier (n + 1) × (n + 1)-Matrizen ausdrücken. ⎛ 1 ⎜ (1) h ⎜ 0 T=⎜ ⎜ .. ⎝ . (n) h0 h1 .. ··· ··· .. h1 · · · hn 0 (1) (n) ⎞ ⎛ 1 − z1 − z2 .. ⎜ ⎜ ⎟ ⎜ ⎟·⎜ ⎟ ⎜ ⎠ ⎜ ⎜ ⎝ −z (n) 0 (1) ⎟ hn .. n −1 −zn ⎞ ··· 0 0 · · · 0 0⎟ ⎟ · · · 0 0⎟ ⎟ . ⎟ .. ⎟ ⎟ 0 0 · · · 1 0⎠ 0 0 ··· 0 1 0 1 0 .. 0 0 1 Das transformierte Polyeder [ T ] P ist im positiven Orthanten enthalten.

Download PDF sample

Rated 4.15 of 5 – based on 23 votes