Rolf Klein's Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen PDF

By Rolf Klein

ISBN-10: 3540209565

ISBN-13: 9783540209560

Wie bestimmt guy in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen berechnen? Wie findet guy ein Ziel in unbekannter Umgebung?

Mit solchen und ähnlichen Fragen beschäftigt sich die Algorithmische Geometrie, ein Teilgebiet der Informatik, dessen Entwicklung etwa 1975 begann und seitdem einen stürmischen Verlauf genommen hat.

Dieses Lehrbuch gibt eine Einführung in häufig verwendete algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive examine. Es stellt wichtige geometrische Strukturen vor wie konvexe Hülle, Voronoi-Diagramm und Delaunay-Triangulation sowie höherdimensionale Datenstrukturen.

Die vorliegende zweite Auflage wurde gründlich überarbeitet. Sie enthält über 60 Übungsaufgaben mit Lösungen. Ferner bietet ein Geometrie-Labor mit Java-Applets die Möglichkeit, mit geometrischen Strukturen und Algorithmen zu experimentieren.

Show description

Read or Download Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen PDF

Similar discrete mathematics books

Download e-book for iPad: Discrete Mathematics for Computer Science by Gary Haggard, John Schlipf, Sue Whitesides

More and more machine scientists from different parts are utilizing discrete mathematical buildings to provide an explanation for recommendations and difficulties. according to their educating studies, the authors provide an available textual content that emphasizes the basics of discrete arithmetic and its complicated subject matters. this article indicates tips to show special principles in transparent mathematical language.

New PDF release: The numerical solution of systems of polynomials arising in

Written via the founders of the hot and increasing box of numerical algebraic geometry, this can be the 1st booklet that makes use of an algebraic-geometric method of the numerical answer of polynomial platforms and in addition the 1st one to regard numerical tools for locating confident dimensional resolution units. The textual content covers the entire concept from equipment constructed for remoted options within the 1980's to the latest learn on confident dimensional units.

Download PDF by Richard A. Brualdi: Combinatorial Matrix Theory (Encyclopedia of Mathematics and

The booklet bargains with the numerous connections among matrices, graphs, diagraphs and bipartite graphs. the fundamental conception of community flows is constructed with a view to receive lifestyles theorems for matrices with prescribed combinatorical houses and to procure numerous matrix decomposition theorems. different chapters disguise the everlasting of a matrix and Latin squares.

Download PDF by Janet Whalen Kammeyer: Restricted Orbit Equivalence for Actions of Discrete

This monograph deals a vast investigative instrument in ergodic thought and measurable dynamics. the incentive for this paintings is that one may possibly degree how comparable dynamical structures are by means of asking how a lot the time constitution of orbits of 1 method has to be distorted for it to develop into the opposite. assorted regulations at the allowed distortion will bring about diverse constrained orbit equivalence theories.

Extra info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

Cn , d) bilden und in speziellen Speicherzellen ablegen. Nach Aufruf eines speziellen Orakelbefehls enth¨ alt der Akkumulator den Wert 1 oder 0, je nach Ausgang des Vorzeichentests c1 x1 + . . + cn xn + d < 0? Elementtest Hierf¨ ur wird nur ein Rechenschritt veranschlagt. Folgender Satz erlaubt es, f¨ ur verschiedene Probleme untere Schranken im linearen Modell anzugeben. Wir betrachten dazu zun¨ achst einen neuen Problemtyp, den Elementtest. Gegeben7 ist eine Menge W im IRn . Es soll ein Verfahren angegeben werden, das f¨ ur ein beliebiges x ∈ IRn entscheidet, ob x in W liegt.

Wenn dann die Sehne pq durch den Mittelpunkt des Kreises geht, so ist α = β = π/2. Zum Schluß dieses Abschnitts u ¨ ber geometrische Grundlagen wollen wir noch ein paar praktische Hinweise und Beispiele geben. Bei der algorithmischen L¨osung geometrischer Probleme treten gewisse Elementaroperationen auf, die zum Teil viele Male auszuf¨ uhren sind. Zum Beispiel soll bestimmt werden, auf welcher Seite einer Geraden im IR2 ein gegebener Punkt liegt (siehe unten bei Halbebenentest). 2 Ein paar Grundbegriffe r p π α≤− 2 α β π β≥− 2 α β r´ q Abb.

Gegeben sind n reelle Zahlen x1 , . . , xn und ein ε > 0. Gefragt ist, ob es Indizes i = j gibt, so daß |xi − xj | < ε gilt. Hat man die n Zahlen erst ihrer Gr¨oße nach sortiert, so l¨aßt sich die Frage leicht in linearer Zeit beantworten: Es gen¨ ugt, jeweils die Nachbarn in der aufsteigenden Folge xπ(1) ≤ xπ(2) ≤ . . ≤ xπ(n) ε-closeness 39 40 Kapitel 1 Grundlagen zu testen. 8 Wir k¨ onnen nun zeigen, daß es keine schnellere L¨osung gibt. 6 Das Problem ε-closeness hat im linearen Modell die Zeitkomplexit¨at Θ(n log n).

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein


by Anthony
4.4

Rated 4.09 of 5 – based on 17 votes