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

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

Best discrete mathematics books

Download PDF by Susanna S. Epp: Discrete Mathematics with Applications (4th Edition)

Susanna Epp's DISCRETE arithmetic WITH functions, FOURTH version presents a transparent creation to discrete arithmetic. popular for her lucid, available prose, Epp explains advanced, summary techniques with readability and precision. This publication provides not just the foremost issues of discrete arithmetic, but in addition the reasoning that underlies mathematical inspiration.

Get Algebra und Diskrete Mathematik für Informatiker PDF

Algebra und Diskrete Mathematik gehören zu den wesentlichen Grundlagen der Informatik. Sie sind unverzichtbare Werkzeuge eines jeden Informatikers und spielen daher auch im Studium eine zentrale Rolle. Dieses Lehrbuch vermittelt anschaulich und leicht nachvollziehbar die wichtigsten algebraischen Grundlagen der Informatik bis hin zur Gleichungstheorie der Universellen Algebra.

Get Combinatorial and geometric group theory: Edinburgh, 1993 PDF

The papers during this e-book signify the present nation of information in workforce idea. It comprises articles of present curiosity written by way of such students as S. M. Gersten, R. I. Grigorchuk, P. H. Kropholler, A. Lubotsky, A. A. Razborov and E. Zelmanov. The contributed articles, all refereed, hide a variety of subject matters in combinatorial and geometric workforce concept.

Additional info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Example text

Verwendet man statt dessen den Algorithmus A, so hat dieser Faktor ur n = 218 ist er schon gr¨oßer als f¨ ur n = 215 den Wert 1,885, f¨ 1,9. Prognosen wie diese lassen sich u ¨ brigens auch ohne Kenntnis der Konstanten C machen, die sich in der O-Notation verbirgt; zur Absch¨ atzung der absoluten Rechenzeit wird aber der Wert von C (oder zumindest eine gute N¨aherung) ben¨otigt. Die Frage nach der Komplexit¨at eines Problems f¨ uhrt zuweilen zur Entdeckung eines Algorithmus, dessen Laufzeitverhalten zwar gr¨ oßenordnungsm¨ aßig optimal ist, der aber trotzdem nicht praktikabel ist.

Erst recht kann der Kreis K(e) durch p und q mit Mittelpunkt im mittleren Punkt von e außer p und q keinen anderen Punkt im Innern oder auf dem Rand enthalten. Angenommen, e w¨ urde von einer anderen Kante e von G gekreuzt, die zwei Punkte r, s miteinander verbindet. Dann l¨agen r und s außerhalb von K(e), und ebenso l¨ agen p und q außerhalb von K(e ). Das k¨ onnte nur gelten, wenn die beiden Kreise K(e) und K(e ) sich (mindestens) viermal kreuzen. Zwei nicht zusammenfallende Kreise haben aber h¨ ochstens zwei Schnittpunkte!

H. die entgegen dem Uhrzeigersinn), sonst ergibt sich der negative Fl¨acheninhalt. Hat daher die Determinante einen positiven Wert, so liegt r links von der orientierten Geraden g. Der Wert ist genau dann gleich 0, wenn r auf g liegt. 15 dargestellt ist. ¨ Bei diesen Uberlegungen sind wir stillschweigend davon ausgegangen, daß wir mit reellen Zahlen exakt rechnen k¨onnen, was in der Praxis schon an der Endlichkeit der Zahldarstellung scheitern muß. Mit rationalen Zahlen kann man im Prinzip beliebig genau rechnen.

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein


by Thomas
4.5

Rated 4.84 of 5 – based on 26 votes