Download e-book for iPad: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein

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

Similar discrete mathematics books

Maria Manzano, Ruy J. G. B. de Queiroz's Model Theory PDF

Formal good judgment, unfastened from the ambiguities of common languages, is mainly suited to use in computing. In flip, version thought, that is excited by the connection among mathematical buildings and good judgment, now has a variety of purposes in parts reminiscent of computing, philosophy, and linguistics.

Computational recreations in Mathematica - download pdf or read online

Offers a few universal difficulties in arithmetic and the way they are often investigated utilizing the Mathematica machine approach. difficulties and routines contain the calendar, sequences, the n-Queens difficulties, electronic computing, blackjack and computing pi. This booklet is for those who want to see how Mathematica is utilized to real-world arithmetic.

Download e-book for kindle: Mathematical Programming And Game Theory For Decision Making by S K Neogy

This edited e-book offers contemporary advancements and state of the art assessment in a number of parts of mathematical programming and video game thought. it's a peer-reviewed study monograph lower than the ISI Platinum Jubilee sequence on Statistical technology and Interdisciplinary study. This quantity presents a breathtaking view of thought and the functions of the equipment of mathematical programming to difficulties in data, finance, video games and electric networks.

Additional resources for Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Sample text

Beim analytischen Ansatz mißt man nicht die Ausf¨ uhrungszeit auf einem konkreten Prozessor, sondern betrachtet die Anzahl der Schritte, die eine idealisierte Maschine bei Ausf¨ uhrung eines Algorithmus zur L¨osung eines Problems der Gr¨oße n machen w¨ urde. Dieses Maschinenmodell sollte m¨oglichst einfach sein, um die Analyse zu erleichtern. 2 Ein paar Grundbegriffe In der Algorithmischen Geometrie wird als Modell oft die REAL RAM verwendet, eine random access machine, die mit reellen Zahlen rechnen kann.

Deshalb beginnen wir nicht mit einer abstrakten Definition, sondern untersuchen typische Beispiele von Sweep-Algorithmen. Dabei halten wir die Augen nach Gemeinsamkeiten offen und wer- sweep als Paradigma divide and conquer als Paradigma 52 Kapitel 2 Das Sweep-Verfahren den im Laufe dieses Kapitels eine Reihe von typischen Merkmalen dieses Verfahrens erkennen. 1 Bestimmung des Maximums Das Maximum einer Menge von Objekten Die denkbar einfachste Anwendung des Sweep-Verfahrens ist aus der Programmierung wohlvertraut: Gegeben sind n Objekte q1 , .

Xn ) = 0 wird eine Hyperebene im IRn definiert, falls nicht alle ci gleich Null sind. Der Test h(x1 , . . “ entscheidet, in welchem der ” beiden offenen Teilr¨aume, die von der Hyperebene getrennt werden, der Punkt (x1 , . . , xn ) liegt. Vergleiche xi < xj sind damit nat¨ urlich immer noch m¨oglich. Als Hardwarebasis k¨onnen wir uns eine REAL RAM vorstellen, die keinen direkten Zugriff auf die Zahlenfolge (x1 , . . , xn ) hat. Sie kann lediglich auf beliebige Weise reelle Koeffizienten (c1 , .

Download PDF sample

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen by Rolf Klein


by George
4.3

Rated 4.79 of 5 – based on 47 votes

admin