Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, - download pdf or read online

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

Similar applied mathematicsematics books

Nolo's Quick LLC: All You Need to Know About Limited by Anthony Mancuso PDF

Written via America's best LLC specialist! for those who run your individual enterprise, you could have most likely heard approximately constrained legal responsibility businesses. enterprise vendors who function LLCs usually are not in my view answerable for enterprise accounts. yet is an LLC good for you? Nolo's fast LLC offers crucial details for company vendors in each nation.

Get Vector Models for Data-Parallel Computing (Artificial PDF

Vector versions for Data-Parallel Computing describes a version of parallelism that extends and formalizes the Data-Parallel version on which the relationship desktop and different supercomputers are dependent. It provides many algorithms in keeping with the version, starting from graph algorithms to numerical algorithms, and argues that data-parallel types aren't merely useful and will be utilized to a shockingly wide selection of difficulties, also they are compatible for very-high-level languages and bring about a concise and transparent description of algorithms and their complexity.

Read e-book online A Complete Guide to PivotTables: A Visual Approach, 1st PDF

Pivot Tables are strong info research instruments, but so much Excel clients do not use them to their fullest capability. an entire consultant to PivotTables indicates you why Pivot Tables are so flexible for info research and the way you could leverage Pivot Tables to swiftly spot traits and make quick company judgements on mountains of knowledge.

Francisco Milton Mendes Neto, Pedro Fernandes Ribeiro Neto's Designing Solutions-Based Ubiquitous and Pervasive PDF

As info availability pervades each element of existence, new developments, applied sciences, and improvements needs to be conscientiously researched, evaluated and carried out as a way to fabricate profitable computing functions. Designing Solutions-Based Ubiquitous and Pervasive Computing: New matters and tendencies examines present practices and demanding situations confronted through designers of Ubiquitous and Pervasive Computing tasks.

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

Sample text

Xπ(n) ε-closeness 39 40 Kapitel 1 Grundlagen zu testen. 8 Wir k¨ onnen nun zeigen, daß es keine schnellere L¨osung gibt. 6 Das Problem ε-closeness hat im linearen Modell die Zeitkomplexit¨at Θ(n log n). Beweis. Offenbar ist ε-closeness ein Elementtestproblem f¨ ur die Menge W = {(x1 , . . , xn ) ∈ IRn ; f¨ ur alle i = j ist |xi − xj | ≥ ε}. Wir zeigen, daß die Zusammenhangskomponenten von W genau die n! vielen Mengen Wπ = {(x1 , . . , xn ) ∈ W ; xπ(1) < xπ(2) < . . < xπ(n) } sind, wobei π alle Permutationen der n Indizes durchl¨auft.

In denen h(x1 , . . , xn ) ein Polynom vom Grad d ≥ 1 ist? 5 auf solche Tests zu verallgemeinern, stoßen wir auf ein Problem: Die Mengen Ab aller Punkte im IRn , f¨ ur die ein Algorithmus A in demselben Blatt b seines Entscheidungsbaums terminiert, ist nicht mehr Schnitt von linearen Halbr¨ aumen und auch nicht mehr konvex! 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 , .

Wir definieren dann 1 TA (P ) = r(n) TA (P, z) 2 z als die zu erwartende Schrittzahl von A bei Bearbeitung von P . An den u ¨ brigen Definitionen ¨andert sich nichts. Entsprechend wird der Speicherplatzbedarf definiert. Wenn wir hervorheben wollen, daß ein Algorithmus nicht mit Randomisierung arbeitet, nennen wir ihn deterministisch. Randomisierte Algorithmen sind oft viel einfacher als ihre deterministischen Konkurrenten. Sie werden uns an mehreren Stellen begegnen. In diesem Buch werden ausschließlich sequentielle Algorithmen betrachtet.

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, 2. Auflage by Rolf Klein


by Ronald
4.2

Rated 4.69 of 5 – based on 47 votes