Read e-book online Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, 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 or Download Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, 2. Auflage PDF

Similar applied mathematicsematics books

Download e-book for iPad: Fragmenting Societies: A Comparative Analysis of Regional by David C. Thorns

David Thorns questions even if the present alterations in capitalist societies are forces of fragmentation. via a comparative ancient research of Australia, New Zealand and Britain, he examines the restructuring of the team, the shift in the direction of extra versatile paintings practices, the increase in unemployment, the expansion of individualism, the diversification of areas and localities, and the construction of latest types of the recent foreign department of work thesis.

Get Spatial Complexity and Territorial Governance (Rtpi Library PDF

City Complexity and Spatial recommendations develops vital new relational and institutionalist ways to coverage research and making plans, of relevance to all people with an curiosity in towns and concrete components. Well-illustrated chapters weave jointly conceptual improvement, event and implications for destiny perform and tackle the problem of city and metropolitan making plans and improvement.

Read e-book online Affect Imagery Consciousness: The Complete Edition: (v. 1 - PDF

". .. amazing. .. "--Malcolm Gladwell, writer of Blink Tomkins's magnum opus, impact Imagery attention, used to be released by means of Springer Publishing corporation in 4 volumes over 30 years. while Tomkins begun writing the e-book within the 1950's, American psychology was once ruled by way of psychoanalytic and behaviorist theories--neither of which positioned a lot value at the position of easy feelings in daily human habit.

Download PDF by Avril Maddrell: Complex Locations (RGS-IBG Book Series)

This enlightening ebook makes noticeable the lives and works of girls who performed a serious function within the improvement of geography as a tutorial box. a unprecedented and exact research of the geographical paintings of 30 person girls geographers from 1850 to 1970 comprises oral histories from girls who've held appointments in British universities given that global struggle II Makes the paintings of ladies geographers obvious and demanding situations the concept of pre Seventies geography as an overwhelmingly masculine box Makes an incredible contribution to debates concerning the theoretical and methodological framing of the historiography of geography

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

Sample text

Es bezeichnen f , g Funktionen von den nat¨ urlichen Zahlen in die nicht-negativen reellen Zahlen. Man definiert: O(f ) = { g; es gibt n0 ≥ 0 und C > 0, so daß g(n) ≤ Cf (n) f¨ ur alle n ≥ n0 gilt }, obere Schranke und f¨ ur ein g ∈ O(f ) sagt man: g ist (in) groß O von f“. Inhaltlich ” bedeutet das, daß fast u ¨ berall die Funktion g durch f nach oben beschr¨ ankt ist – bis auf einen konstanten Faktor. Man erlaubt endlich viele Ausnahmestellen n < n0 , damit man auch solche Funktionen f als obere Schranken verwenden kann, die f¨ ur kleine Werte von n den Wert Null annehmen.

45 46 Kapitel 1 Grundlagen (ii) Ein solcher geschlossener Weg w¨ urde eine Folge p0 , p1 , . . pn−1 , pn = p0 von Punkten aus S durchlaufen, bei der f¨ ur jedes i, 0 ≤ i ≤ n − 1, gilt: pi+1 ist der n¨achste Nachbar von pi oder pi ist der n¨achste Nachbar von pi+1 . Angenommen, es gilt f¨ ur jedes i die erste Eigenschaft. 21 (i) gezeigte Struktur; dabei weisen die Pfeile jeweils zum n¨achsten Nachbarn. p4 pn-1 pi pi-1 p3 pn=p0 pi+1 pj+1 p2 p1 pj+1 (i) pj (ii) Abb. 21 Wenn in (i) stets |pi pi +1 | > |pi+1 pi+2 | gilt, kann nicht gleichzeitig pn = p0 sein.

Ein Bin¨ arbaum T mit m ≥ 2 Bl¨attern hat zwei Teilb¨ aume mit m1 und m2 Bl¨ attern, wobei m = m1 + m2 ist. F¨ ur die Pfadl¨ angen hi , kj der Teilb¨aume gilt nach Induktionsvoraussetzung m1 2−hi = 1 und i=1 m2 2−kj = 1. j=1 Weil in T alle Pfade um 1 l¨ anger sind, folgt m v=1 2−lv = 2−1 ( m1 i=1 2−hi + m2 j=1 2−kj ) = 1. 49 50 Kapitel 1 Grundlagen (ii) Die Ungleichung vom geometrischen und arithmetischen Mittel besagt f¨ ur die Zahlen 2−li 1 m m 2−li ≥ m 2−li . m i=1 i=1 Die linke Seite ist nach (i) gleich 1 m m 2−li = i=1 1 , m f¨ ur die rechte ergibt sich m l 2 − mi =2 1 −m m i=1 li , i=1 und es folgt m≤2 1 m m i=1 li .

Download PDF sample

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


by Mark
4.3

Rated 4.54 of 5 – based on 13 votes