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

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

Best applied mathematicsematics books

Coupled Data Communication Techniques for High-Performance and Low-Power Computing

Designers of next-generation high-performance computers face a bunch of technical demanding situations. For the prior a number of many years, emerging clock frequencies and elevated chip integration have fueled the expansion of computing device functionality. Now those traits have slowed: strength and complexity constrains additional raises in clock frequencies, and financial realities restrict the velocity of Moore's legislation.

Peace Psychology: A Comprehensive Introduction

A entire creation to the swiftly starting to be study zone of peace psychology. either a subject in its personal correct and studied inside classes on peace reports, clash reviews and subsidiaries of psychology, diplomacy and politics, peace psychology is a essentially and theoretically very important zone.

The Complete Idiot's Guide to Spices and Herbs

Zest it up! utilizing spices and herbs—the key to any scrumptious meal—can be daunting with such a lot of to select from, let alone the numerous attainable combos. during this publication, a grasp chef and baker unlocks the main to the extraordinary global of style by means of displaying chefs of each point tips on how to use and mix over one hundred fifty of the preferred spices and herbs.

Stem Cells - No. 265: Nuclear Reprogramming and Therapeutic Applications (CIBA Foundation Symposia Series)

Figuring out stem cells on the molecular point is vital to realizing their behaviour in a physiological context. This quantity in our acclaimed Novartis starting place sequence good points lively dialogue from the world’s specialists during this subject at the vital moral concerns which are raised through study on stem cells.

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

Sample text

2 Ein Weg w, der aus einer endlichen Folge von Liniensegmenten pq, qr, . . , tu, uv besteht, heißt eine polygonale Kette. Ist w eine einfache, geschlossene polygonale Kette in der Ebene, so heißt das von w umschlossene innere Gebiet zusammen mit w ein Polygon, P . 3 Die Liniensegmente in w heißen die Kanten von P , ihre Endpunkte heißen Ecken von P (wir k¨ onnen P auch als kreuzungsfreien geometrischen Graphen auffassen und m¨ ußten die Ecken dann Knoten“ nennen; der ” Begriff Ecke“ ist aber gebr¨auchlicher).

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. Was passiert, wenn wir auch Multiplikation und Division der Eingabezahlen erlauben, damit also auch Tests der Art h(x1 , .

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. W¨are er planar, w¨ urde mit der Eulerschen Formel f = 5 folgen. 19. Um zu einem Widerspruch zu gelangen, nutzen wir aus, daß der Graph K3,3 schlicht ist und keine Kreise ungerader L¨ange enthalten kann; denn wenn man von einem Knoten a der Menge A startet, muß man eine gerade Anzahl von Kanten besuchen, bevor man wieder in a ankommt.

Download PDF sample

Rated 4.19 of 5 – based on 25 votes