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

Posted by

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, 2. Auflage PDF

Similar applied mathematicsematics books

Intergovernmental Cooperation: Rational Choices in Federal Systems and Beyond (Comparative Politics)

Over the last many years, governments have more and more been faced with difficulties that go beyond their limitations. a large number of coverage fields are affected, together with setting, alternate and protection. Responding to the demanding situations prompted via Europeanization and globalization, governments more and more have interaction throughout various spheres of authority.

Continuity and Change in the Baltic Sea Region: Comparing Foreign Policies (On the Boundary of Two Worlds: Identity, Freedom, & Moral Imagination in the Baltics)

Continuity and alter within the Baltic Sea zone uncovers the Baltic States' overseas coverage transition from Socialist Republics to ecu member-states. positioned among the Russian Federation and northerly Europe, Estonia, Latvia and Lithuania have needed to manoeuvre inside a frequently tender sub-region. on account that independence, the overseas rules of the Baltic States were ruled by means of de-Sovietization and ecu integration.

Additional info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, 2. Auflage

Example text

3 (i) Nein! F¨ ur eine kreuzungsfreie geometrische Einbettung in der Ebene oder auf der Kugeloberfl¨ache w¨ urde nach der Eulerschen Formel gelten v − e + f = c + 1. Nun ist v = 5 und e = 10, weil von jedem der 5 Knoten genau 4 Kanten ausgehen. Außerdem ist K5 zusammenh¨angend, also c = 1. Daraus folgt f = 7. 3, und wir erhalten den Widerspruch 20 = 2e ≥ 3f = 21. 18 zeigt. Abb. 18 Eine kreuzungsfreie Realisierung von K5 auf dem Torus. 4 Nein! F¨ ur den Graphen K3,3 gilt offenbar v = 6, e = 9 und c = 1.

Xn ) < 0} {(x1 , . . , xn ) ∈ IRn ; h(x1 , . . , xn ) ≥ 0}. Weil diese Teilr¨ aume konvex sind, ist auch Ab konvex, insbesondere also zusammenh¨angend. F¨ ur alle Punkte x in Ab trifft Algorithmus A dieselbe Entscheidung; folglich gilt entweder Ab ⊂ W oder Ab ∩ W = ∅. Außerdem ist IRn = Ab , b Blatt da der Algorithmus ja f¨ ur jede Eingabe x eine Entscheidung treffen muß. Daraus folgt: W = IRn ∩ W Ab ∩ W = b Blatt = Ab b∈B f¨ ur eine bestimmte Teilmenge B aller Bl¨atter des Entscheidungsbaums E.

2 Ein paar Grundbegriffe mischen Geometrie interessiert, sei z. B. auf Dehne und Sack [40] verwiesen. 5 Untere Schranken Ein Problem hat die Zeitkomplexit¨at Ω(f ), wenn es f¨ ur jeden Algorithmus eine Konstante c > 0 gibt, so daß sich f¨ ur jedes hinreichend große n Beispiele der Gr¨oße n finden lassen, f¨ ur deren L¨ osung der Algorithmus mindestens cf (n) viele Schritte ben¨otigt. Die Funktion f heißt dann eine untere Schranke f¨ ur das Problem. Manchmal lassen sich triviale untere Schranken f sehr leicht angeben.

Download PDF sample

Rated 4.49 of 5 – based on 39 votes