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

Download e-book for kindle: Triangulations: Structures for Algorithms and Applications by Jesús A. De Loera, Jörg Rambau, Francisco Santos

Triangulations look all over, from quantity computations and meshing to algebra and topology. This ebook stories the subdivisions and triangulations of polyhedral areas and element units and provides the 1st entire remedy of the idea of secondary polytopes and comparable issues. A important subject of the publication is using the wealthy constitution of the distance of triangulations to resolve computational difficulties (e.

New PDF release: Algebra und Diskrete Mathematik

Algebra und Diskrete Mathematik geh? ren zu den wichtigsten mathematischen Grundlagen der Informatik. Dieses zweib? ndige Lehrbuch f? hrt umfassend und lebendig in den Themenkomplex ein. Dabei erm? glichen ein klares Herausarbeiten von L? sungsalgorithmen, viele Beispiele, ausf? hrliche Beweise und eine deutliche optische Unterscheidung des Kernstoffs von weiterf?

Harris Kwong's A Spiral Workbook for Discrete Mathematics PDF

It is a textual content that covers the normal subject matters in a sophomore-level path in discrete arithmetic: common sense, units, evidence recommendations, simple quantity thought, services, kin, and ordinary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in arithmetic, and publications the scholars via a close dialogue on how an explanation is revised from its draft to a last polished shape.

Additional info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

Vom dritten bis zum siebten Tag steigt der Kurs der Aktie insgesamt um den Wert 10. Durch Ausprobieren der anderen M¨oglichkeiten kann man sich davon u uckenlose Teilfolge von Zahlen ¨ berzeugen, daß es keine l¨ gibt, die eine gr¨oßere Summe h¨atte. So lohnt es sich zum Beispiel nicht, die Aktie auch am achten Tag noch zu behalten, weil der Verlust von 9 sp¨ater nicht mehr ausgeglichen wird. Summe = 10 2 -4 3 ✻ 1 ✻ 3 -1 4 -1 5 -9 2 ✻ 7 -6 5 -3 5 ✻ n Abb. 1 Die maximale Teilsumme aufeinanderfolgender Zahlen hat hier den Wert 10.

Der duale Graph G∗ ist kreuzungsfrei. Weil in G alle Fl¨ achen von mindestens 3 Kanten berandet sind, hat jeder Knoten von G∗ einen Grad ≥ 3. 2. ur G daher e < 3v. Mit (i) oder Wegen e∗ = e und f ∗ = v gilt f¨ direkt aus v ∗ < 2f ∗ folgt f < 2v. (iii) Nein! 22 hat nur einen Knoten, aber e Kanten und e + 1 Fl¨ achen. Abb. 22 Ein Graph, der nicht schlicht ist, kann viele Fl¨ achen und Kanten und wenige Knoten besitzen. 7 Nein! Gegenbeispiel: K1 = {(x, y); x < 0 oder (x = 0 und y > 0)} K2 = {(x, y); x > 0 oder (x = 0 und y < 0)}.

Qπ(n) zu diesem Blatt f¨ uhren. F¨ ur jede Permutation muß ein Blatt vorhanden sein. Der Entscheidungsbaum hat daher mindestens n! ) ≥ log2 ≥ ≥ n 2 n 2 n 2 n log2 2 1 ur alle n ≥ 8. n log2 n f¨ 3 Es gibt also eine Permutation, f¨ ur die das Verfahren A mindestens 1 n log n viele Vergleiche ausf¨ u hrt. ✷ 2 3 Weil man mit Heapsort oder Mergesort in Zeit O(n log n) sortieren kann, hat das Sortierproblem die Komplexit¨at Θ(n log n). 12 Sei T ein Bin¨arbaum mit m Bl¨attern, und seien l1 , . . , lm die L¨ ange der Pfade von der Wurzel zu den Bl¨ attern.

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein


by Brian
4.2

Rated 4.12 of 5 – based on 48 votes