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.
Read Online or Download Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen PDF
Similar discrete mathematics books
Computational Complexity of Sequential and Parallel Algorithms
This booklet provides a compact but finished survey of significant leads to the computational complexity of sequential algorithms. this can be by means of a hugely informative advent to the improvement of parallel algorithms, with the emphasis on non-numerical algorithms. the fabric is so chosen that the reader in lots of instances is ready to persist with an identical challenge for which either sequential and parallel algorithms are mentioned - the simultaneous presentation of sequential and parallel algorithms for fixing allowing the reader to recognize their universal and detailed positive factors.
Discontinuum Mechanics : Using Finite and Discrete Elements
Textbook introducing the mathematical and computational thoughts of touch mechanics that are used more and more in commercial and educational software of the mixed finite/discrete aspect strategy.
Matroids: A Geometric Introduction
Matroid concept is a colourful sector of analysis that gives a unified strategy to comprehend graph conception, linear algebra and combinatorics through finite geometry. This booklet presents the 1st entire advent to the sector with the intention to entice undergraduate scholars and to any mathematician attracted to the geometric method of matroids.
Fragile networks: Identifying Vulnerabilities and Synergies in an Uncertain World
A unified therapy of the vulnerabilities that exist in real-world community systems-with instruments to spot synergies for mergers and acquisitions Fragile Networks: deciding upon Vulnerabilities and Synergies in an doubtful international offers a accomplished examine of community platforms and the jobs those structures play in our daily lives.
Extra info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen
Example text
Aus demselben Grund kann nicht f¨ ur jedes i die zweite Bedingung gelten. 21 (ii) gezeigt. Dieser Punkt pi h¨atte dann zwei n¨achste Nachbarn – ein Widerspruch zur Voraussetzung. Wenn also G keinen geschlossenen Weg enth¨alt, so erst recht keine seiner Zusammenhangskomponenten. Jede von ihnen ist folglich ein Baum. (iii) Nein. Wenn die n¨achsten Nachbarn eindeutig sind, besteht der Graph G wegen Teilaufgabe (ii) aus lauter B¨aumen. Sei T einer dieser B¨aume. Aus jedem seiner v Knoten f¨ uhrt genau eine Kante heraus; bei dieser Betrachtung werden genau die d Kanten doppelt erfaßt, die in beide Richtungen orientiert sind.
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). Beweis. 6 unm¨ oglich ist. ✷ Hier haben wir ein Beispiel, wie man ein Problem auf ein anderes reduziert, um neue untere Schranken zu beweisen. Im linearen Modell haben wir erlaubt, Linearkombinationen der reellen Eingabezahlen x1 , . . , xn auf ihr Vorzeichen zu testen, und gesehen, daß sich dadurch keine schnelleren Sortierverfahren f¨ ur reelle Zahlen ergeben.
Diese Gerade wird f¨ ur uns sp¨ater von Interesse sein, weil sie aus genau den Punkten besteht, die zu p und q denselben Abstand haben. 15 (i). Die Gerade B(p, q) muß durch den Mittelpunkt m = 12 (p + q) von pq laufen; wir machen daher den Ansatz B(p, q) = {m + al; a ∈ IR} f¨ ur die parametrisierte Darstellung, wobei der Vektor l = (l1 , l2 ) noch zu bestimmen ist. Weil l auf pq senkrecht steht, muß f¨ ur das Skalarprodukt gelten l1 (q1 − p1 ) + l2 (q2 − p2 ) = 0. Vermeidung unn¨ otiger Berechnungen Bisektor 25 26 Kapitel 1 Grundlagen Es mag naheliegend erscheinen, nun l1 = 1 und l2 = p1 − q1 q2 − p2 in die Darstellung von B(p, q) einzusetzen.