Download Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein PDF

By Rolf Klein

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 Online or Download Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen PDF

Similar discrete mathematics books

Matroid Decomposition

Matroids, first outlined in 1935, are an summary generalization of graphs and matrices. by way of now, there's a huge physique of matroid thought. The e-book covers the a part of the speculation facing composition and decomposition of matroids. The ebook is a revised model of the unique ebook of 1992. It doesn't suppose any past wisdom of matroid idea.

Direct methods for sparse matrices

The topic of sparse matrices has its root in such assorted fields as administration technology, strength platforms research, surveying, circuit thought, and structural research. effective use of sparsity is a key to fixing huge difficulties in lots of fields. This publication offers either perception and solutions for these trying to remedy those difficulties.

Additional info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

B. all nearest neighbors), und sei P ∈ Π ein Beispiel des Problems der Gr¨oße |P | = n (also z. B. eine konkrete Menge von n Punkten in der Ebene). Ist dann A ein Algorithmus zur L¨ osung des Problems Π, in RAM-Anweisungen formuliert, so bezeichnet TA (P ) die Anzahl der Schritte, die die RAM ausf¨ uhrt, um die L¨ osung f¨ ur das Beispiel P zu berechnen. 5 Vom theoretischen Standpunkt aus kann man die RAM als Registermaschine mit abz¨ ahlbar unendlich vielen Registern oder als Turingmaschine mit Halbband ansehen, dessen Felder jeweils einen Buchstaben aus einem unendlichen Alphabet enthalten k¨ onnen.

Ein Test in der endg¨ ultigen Zielumgebung ist sehr aussagekr¨ aftig, vorausgesetzt • es werden vom Typ her solche Beispiele P des Problems Π als Eingabe verwendet, wie sie auch in der realen Anwendung auftreten, und • es wird mit realistischen Problemgr¨oßen gearbeitet. Wird einer dieser Gesichtspunkte vernachl¨assigt, kann es ¨ sp¨ ater zu Uberraschungen kommen. Wer etwa Sortieren durch Einf¨ ugen und Quicksort experimentell miteinander vergleicht und dabei nur Eingabefolgen verwendet, die schon teilweise vorsortiert sind, wird feststellen, daß Sortieren durch Einf¨ ugen besser abschneidet.

Weil die Koordinatenfunktionen stetig differenzierbar sind, gilt nach der Integralformel f¨ ur die L¨ ange der Feder 1 L¨ange (r cos 2kπt) 2 + (r sin 2kπt) 2 + (ht) 2 dt = 0 1 = 4k 2 r2 π 2 (sin2 2kπt + cos2 2kπt) + h2 dt 0 1 4r2 k 2 π 2 + h2 dt = 0 = 4r2 k 2 π 2 + h2 . Nun hat sich die L¨ ange der Feder durch die Belastung nicht ver¨andert, da der elastische Bereich nicht u ¨berschritten wurde. Also muß 4k 2 π 2 + 1 = 4r2 k 2 π 2 + h2 gelten, folglich r2 = 1 − h2 − 1 < 1. 2 (i) Reflexivit¨ at: F¨ ur jedes a ∈ A gilt a ∼ a, weil sich a u ¨ ber den konstanten Weg mit Parametrisierung f (t) = a mit a verbinden l¨ aßt.

Download PDF sample

Rated 4.18 of 5 – based on 42 votes