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

Time for Kids: Nonfiction Comprehension Test Practice Second Edition, Level 3

This sequence, constructed through Dr. Fry, is predicated on articles from TIME for children magazines. actions offer examining comprehension perform in standardized try layout.

Generalized Multipole Techniques for Electromagnetic and Light Scattering (Mechanics and Mathematical Methods - Series of Handbooks)

This ebook is an edited quantity of 9 papers protecting different variations of the generalized multipole recommendations (GMT). The papers have been offered on the fresh third Workshop on Electromagnetics and light-weight Scattering - thought and functions, which interested in present GMT equipment. those contain the a number of multipole approach (MMP), the discrete resources procedure (DSM), Yasuura's technique, approach to auxiliary assets and null-field strategy with discrete assets.

Stairs 2008: Proceedings of the Fourth Starting AI Researchers’ Symposium

IOS Press is a world technological know-how, technical and clinical writer of top of the range books for teachers, scientists, and execs in all fields. a number of the parts we submit in: -Biomedicine -Oncology -Artificial intelligence -Databases and data platforms -Maritime engineering -Nanotechnology -Geoengineering -All facets of physics -E-governance -E-commerce -The wisdom economic climate -Urban experiences -Arms keep watch over -Understanding and responding to terrorism -Medical informatics -Computer Sciences

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

Sample text

Wir haben es vielmehr nun mit algebraischen (Pseudo-) Mannigfaltigkeiten zu tun, einem klassischen Gegenstand der Algebraischen Geometrie. Eine andere Beobachtung zeigt, daß wir in diesem algebraischen Modell die Kosten eines Tests h(x1 , . . , xn ) > 0? nicht l¨ anger mit nur einem Schritt veranschlagen d¨ urfen. Sonst k¨ onnte n¨ amlich das Problem element uniqueness pl¨otzlich in Zeit O(1) gel¨ ost werden, durch den Test (xi − xj )2 > 0? 0≤i

Das sollte man dann explizit erw¨ ahnen, weil es einen Einfluß auf die prinzipielle Leistungsf¨ ahigkeit des Modells haben kann. Die Ausf¨ uhrung eines jeden Befehls (Rechenoperation, Speicherzugriff oder Test mit Programmsprung) z¨ahlt als ein Elementarschritt der RAM. Dieses Modell ist einem realen Rechner ¨ahnlich, soweit es die prinzipielle Funktionsweise des Prozessors und die Struktur des Hauptspeichers betrifft. Ein wesentlicher Unterschied besteht aber darin, daß in einer Zelle eines realen Hauptspeichers nur ein Wort fester L¨ ange Platz hat und nicht eine beliebig große Zahl.

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 , .

Download PDF sample

Rated 4.51 of 5 – based on 18 votes