Download e-book for kindle: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein

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

Best discrete mathematics books

Read e-book online Maple V Library Reference Manual PDF

The layout and implementation of the Maple procedure is an on-going undertaking of the Symbolic Com­ putation staff on the college of Waterloo in Ontario, Canada. This guide corresponds with model V (roman numeral 5) of the Maple method. The online aid subsystem may be invoked from inside of a Maple consultation to view documentation on particular issues.

Smooth particle applied mechanics : the state of the art - download pdf or read online

This booklet takes readers via all of the steps useful for fixing tough difficulties in continuum mechanics with soft particle equipment. Pedagogical difficulties make clear the new release of preliminary stipulations, the therapy of boundary stipulations, the combination of the equations of movement, and the research of the consequences.

Extra resources for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

13 (ii) illustriert ist. Daneben gilt der Sinussatz. Sind p und q zwei Punkte im IRd , so gilt f¨ ur ihr Skalarprodukt p · q d pi qi = p · q = |p| |q| cos α, i=1 positive Richtung orthogonal Satz des Thales Elementaroperationen wobei α den Winkel zwischen ihren Ortsvektoren am Nullpunkt bezeichnet. Allgemein ist f¨ ur die Winkelmessung (und f¨ ur das Durchlaufen geschlossener Kurven in der Ebene) die positive Richtung gegen den Uhrzeigersinn; beim Skalarprodukt kommt es aber auf die Reihenfolge von p und q nicht an.

Xn ) hat. Sie kann lediglich auf beliebige Weise reelle Koeffizienten (c1 , . . , 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.

Fn (a)) element uniqueness geh¨ ort dann aber nicht zur Menge W . 5. ✷ Ganz analog l¨aßt sich ein ¨ahnliches Problem behandeln, das den Namen element uniqueness tr¨agt. Gegeben sind wieder n reelle Zahlen x1 , . . , xn , gefragt ist, ob es Indizes i = j mit xi = xj gibt. 8 Sortieren, z. B. mit Heapsort, ben¨ otigt nur Vergleiche. Tests der Art xi − xj − ε < 0 sind im linearen Modell erlaubt. 7 Das Problem element uniqueness hat die Zeitkomplexit¨at Θ(n log n) im linearen Modell. 8 Auch im linearen Modell hat Sortieren die Zeitkomplexit¨at Θ(n log n).

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein


by James
4.3

Rated 4.36 of 5 – based on 21 votes