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 PDF

Similar discrete mathematics books

Handbook of Analytic-Computational Methods in Applied Mathematics

Operating computationally in utilized arithmetic is the very essence of facing real-world difficulties in technology and engineering. Approximation theory-on the borderline among natural and utilized arithmetic- has continually provided probably the most cutting edge principles, computational tools, and unique ways to many varieties of difficulties.

Applied and Computational Complex Analysis: Power Series, Integration, Conformal Mapping, Location of Zeros

At a mathematical point obtainable to the non-specialist, the 3rd of a three-volume paintings exhibits tips on how to use tools of complicated research in utilized arithmetic and computation. The e-book examines two-dimensional capability thought and the development of conformal maps for easily and multiply attached areas.

The Art of Mathematics: Coffee Time in Memphis

Can a Christian get away from a lion? How fast can a rumor unfold? are you able to idiot an airline into accepting oversize luggage? leisure arithmetic is stuffed with frivolous questions the place the mathematician's paintings should be dropped at undergo. yet play usually has a goal. In arithmetic, it might probably sharpen abilities, supply enjoyment, or just shock, and books of difficulties were the stock-in-trade of mathematicians for hundreds of years.

The poset of k-shapes and branching rules for k-Schur functions

The authors supply a combinatorial enlargement of a Schubert homology category within the affine Grassmannian GrSLk into Schubert homology sessions in GrSLk 1. this can be completed by means of learning the combinatorics of a brand new category of walls referred to as k-shapes, which interpolates among k-cores and ok 1-cores. The authors outline a symmetric functionality for every k-shape, and express that they extend certainly when it comes to twin k-Schur capabilities.

Extra resources for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Example text

Dann ist die Federkurve parametrisiert durch f (t) = (r cos 2kπt, r sin 2kπt, ht), 0 ≤ t ≤ 1. Weil die Koordinatenfunktionen stetig differenzierbar sind, gilt nach der Integralformel f¨ ur die L¨ ange der Feder 1 L¨ange (r cos 2kπt) 2 + (r sin 2kπt) 2 + (ht) 2 dt = 0 1 = 4k 2 r2 π 2 (sin2 2kπt + cos2 2kπt) + h2 dt 0 1 4r2 k 2 π 2 + h2 dt = 0 = 4r2 k 2 π 2 + h2 . Nun hat sich die L¨ ange der Feder durch die Belastung nicht ver¨andert, da der elastische Bereich nicht u ¨berschritten wurde. Also muß 4k 2 π 2 + 1 = 4r2 k 2 π 2 + h2 gelten, folglich r2 = 1 − h2 − 1 < 1.

Ist diese Einheit erst vorhanden und richtig verarbeitet, so kann man im n¨achsten Schritt oft auch einen Algorithmus entwickeln, der praktikabel und optimal ist, oder zumindest nicht sehr weit vom Optimum entfernt. Vor diesem Hintergrund wird klar, daß die Ermittlung Prognosen optimal vs. praktikabel 33 34 Kapitel 1 Grundlagen praktische Konsequenzen mittlere Kosten randomisierter Algorithmus deterministischer Algorithmus der genauen Komplexit¨at eines Problems nicht Theorie um ihrer selbst willen ist, sondern zu konkreten Verbesserungen in der Praxis f¨ uhren kann.

7 Nein! Gegenbeispiel: K1 = {(x, y); x < 0 oder (x = 0 und y > 0)} K2 = {(x, y); x > 0 oder (x = 0 und y < 0)}. 8 (i) Ist das Polygon P konvex, ist mit p und x stets auch das Liniensegment px in P enthalten. Wenn umgekehrt jeder Punkt in P jeden anderen sehen kann, k¨ onnen keine spitzen Ecken existieren. Also ist P konvex. (ii) Jede Kante von P kann h¨ochstens eine Kante zu vis(p) beitragen. Sind n¨ amlich die Punkte q und q einer Kante e von P vom 47 48 Kapitel 1 Grundlagen e r q' q P p Abb. 23 W¨ urde ∂P die Sicht von p auf r blockieren, w¨ are einer der Punkte q, q von p aus ebenfalls nicht sichtbar.

Download PDF sample

Rated 4.96 of 5 – based on 26 votes