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

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

Sample text

11 (ii) zeigt ein Polyeder, das sich ” als Vereinigung eines Quaders mit einem Tetraeder ergibt (sowie dessen konvexe H¨ ulle, siehe weiter unten). Eine Teilmenge K vom IRd heißt konvex, wenn sie zu je zwei Punkten p, q auch das Liniensegment pq enth¨alt. Der IRd ist wie auch alle Quader und Kugeln konvex. Eine Teilmenge K der Ebene ist genau dann konvex, wenn durch jeden Punkt p auf dem Rand von K eine Gerade f¨ uhrt, so 2 Hierbei fassen wir Punkte als Ortsvektoren auf; die Multiplikation mit a erfolgt koordinatenweise.

20. 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!

Eine konkrete Menge von n Punkten in der Ebene). Ist dann A ein Algorithmus zur L¨ osung des Problems Π, in RAM-Anweisungen formuliert, so bezeichnet TA (P ) die Anzahl der Schritte, die die RAM ausf¨ uhrt, um die L¨ osung f¨ ur das Beispiel P zu berechnen. 5 Vom theoretischen Standpunkt aus kann man die RAM als Registermaschine mit abz¨ ahlbar unendlich vielen Registern oder als Turingmaschine mit Halbband ansehen, dessen Felder jeweils einen Buchstaben aus einem unendlichen Alphabet enthalten k¨ onnen.

Download PDF sample

Rated 4.30 of 5 – based on 43 votes