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

Similar applied mathematicsematics books

Genocide: A Comprehensive Introduction, Second Edition

A useful creation to the topic of genocide, explaining its heritage from pre-modern instances to the current day, with a large choice of case stories. contemporary occasions within the former Yugoslavia, Rwanda, East Timor and Iraq have tested with appalling readability that the specter of genocide continues to be a massive factor inside of global politics.

Frommer's Hong Kong (2009) (Frommer's Complete) 10th Edition

America’s number one bestselling commute sequence Written by means of greater than a hundred seventy five outspoken tourists around the world, Frommer’s entire courses support tourists event locations the best way locals do. extra every year up to date publications than the other sequence 16-page colour part and foldout map in all annual courses Outspoken evaluations, distinct costs, and advised itineraries Dozens of certain maps in an easy-to-read, two-color layout

Lifetimes of Fluorinated Compounds

Cost constants for reactions of eleven hydrochlorofluorocarbons and 12 hydrofluorocarbons have been measured through absolutely the fee process over the temperature variety 250-430 ok. OH radicals have been generated through flash photolysis, laser photolysis, or a discharge stream tools; and the focus of OH radicals used to be monitored through the laser-induced fluorescence strategy.

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

Example text

H. 10. Das Gegenst¨ uck zum einfachen Polygon ist das einfache Polyeder. Sein Rand – die Oberfl¨ache – besteht aus Polygonen. Jede Kante geh¨ort dabei zu genau zwei Polygonen. Diese Oberfl¨ ache zerlegt den Raum in zwei Gebiete, ein beschr¨anktes inneres und ein unbeschr¨anktes a¨ußeres Gebiet. So wie ein Polygon bis auf Deformation einem Kreis gleicht, l¨aßt sich ein Polyeder zu einer Kugel ausbeulen“. 11 (ii) zeigt ein Polyeder, das sich ” als Vereinigung eines Quaders mit einem Tetraeder ergibt (sowie dessen konvexe H¨ ulle, siehe weiter unten).

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 , . . , in denen h(x1 , .

2 Sweep im Eindimensionalen Das dichteste Paar einer Menge von Zahlen Betrachten wir zum Beispiel das Problem closest pair (vgl. 10) im IR1 f¨ ur n reelle Zahlen x1 , . . , xn . Um zwei Zahlen xi , xj mit minimalem Abstand d(xi , xj ) = |xi − xj | zu bestimmen, m¨ ussen wir nur solche Paare betrachten, die der Gr¨oße nach benachbart sind. Wir sortieren die xi deshalb zun¨achst nach wachsender Gr¨ oße; die sortierte Folge x1 ≤ x2 ≤ . . ≤ xn mit xj = xπ(j) ist die richtige Besuchsreihenfolge f¨ ur einen sweep.

Download PDF sample

Rated 4.14 of 5 – based on 18 votes