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

Best discrete mathematics books

Arpack User's Guide: Solution of Large-Scale Eigenvalue Problems With Implicityly Restorted Arnoldi Methods (Software, Environments, Tools)

A consultant to knowing and utilizing the software program package deal ARPACK to unravel huge algebraic eigenvalue difficulties. The software program defined is predicated at the implicitly restarted Arnoldi strategy, which has been heralded as one of many 3 most crucial advances in huge scale eigenanalysis long ago ten years.

Probabilistic inequalities

"In this monograph, the writer provides univariate and multivariate probabilistic inequalities with assurance on uncomplicated probabilistic entities like expectation, variance, second producing functionality and covariance. those are outfitted at the contemporary classical type of genuine research inequalities that are additionally mentioned in complete information.

Algebraic and Discrete Mathematical Methods for Modern Biology

Written via specialists in either arithmetic and biology, Algebraic and Discrete Mathematical equipment for contemporary Biology deals a bridge among math and biology, offering a framework for simulating, interpreting, predicting, and modulating the habit of advanced organic platforms. every one bankruptcy starts off with a question from smooth biology, via the outline of convinced mathematical tools and conception applicable within the seek of solutions.

Extra info for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

Man definiert 31 untere Schranke Ω-Notation g ∈ Ω(f ) : ⇐⇒ f ∈ O(g) ⇐⇒ es gibt n0 ≥ 0 und c > 0, so daß g(n) ≥ cf (n) f¨ ur alle n ≥ n0 gilt. In unserem Beispiel ist g ∈ Ω(n3 ), erst recht also g ∈ Ω(n2 ). Schließlich verwendet man die Theta-Notation Θ-Notation g ∈ Θ(f ) : ⇐⇒ g ∈ O(f ) und g ∈ Ω(f ), um auszudr¨ ucken, daß g und f etwa gleich groß sind. Diese Be¨ ziehung ist offenbar eine Aquivalenzrelation. F¨ ur die Funktion g 3 von oben gilt g ∈ Θ(n ). Wir sagen, g w¨achst wie n3 oder g hat die Gr¨oßenordnung n3 .

Zu sortieren ist eine Folge von n paarweise verschiedenen Objekten (q1 , . . , qn ) aus einer Menge Q, auf der eine vollst¨andige Ordnung < definiert ist. Wir stellen uns vor, daß die Objekte qi in einem Array gespeichert sind, auf das wir keinen direkten Zugriff haben. Unsere Eingabe besteht aus der Objektanzahl n und einer Funktion K. Ein Aufruf K(i, j) vergleicht die Objekte an den Positionen i und j im Array und liefert folgendes Ergebnis: K(i, j) = 1, falls qi < qj 0, falls qi > qj . Die Sortieraufgabe besteht in der Berechnung derjenigen Permutation π = (π(1), π(2), .

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). ” Polygone treten unter anderem als Grundrisse von R¨aumen auf, in denen sich Roboter bewegen.

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein
Rated 4.74 of 5 – based on 33 votes