Applied Mathematicsematics

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen, by Rolf Klein

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, 2. Auflage PDF

Best applied mathematicsematics books

Stainless Steels for Medical and Surgical Applications (ASTM Special Technical Publication, 1438)

Twenty-one peer reviewed papers provide the most recent learn and technical advancements within the clinical makes use of of stainless steels. This new ebook covers quite a lot of themes together with corrosion, put on, organic reaction, radiopacity, and the excessive fee of clinical items. New alloys are mentioned as recommendations to a few matters by way of supplying extra biocompatible, greater caliber, radiopaque, or economical possible choices for orthopaedic implants and stents.

Convertisseurs et electronique de puissance : Commande, description, mise en oeuvre - Applications avec Labview

Cet ouvrage dresse un huge landscape de l'électronique de puissance : features fondamentaux et résultats expérimentaux, équipements et matériels, outils de perception et mise en oeuvre en milieu industriel. C'est dans cet esprit résolument pragmatique que sont ainsi présentés : les systèmes électroniques de commande, créateurs et transmetteurs, analogique et numérique ; les différents forms de convertisseurs, leurs principes de fonctionnement et leurs comportements dans les stipulations idéales puis réelles ; leurs performances, grâce notamment à los angeles souplesse des systèmes de commande, mais aussi leurs fragilités (en particulier en régime transitoire) ; les outils logiciels (SIMULINK, PSpice et LabVIEW) à même d'accroître los angeles connaissance de leurs comportements et l. a. mise au element de systèmes plus performants.

Management Control in Small and Medium-Sized Enterprises - Indirect Control Forms, Control Combinations and their Effect on Company Performance

Administration keep an eye on is a key functionality completed via managers, despite the fact that a slightly ignored subject in administration study. Jens Hutzshenreuter determines the influence of administration keep watch over varieties at the functionality of cutting edge small and medium-sized businesses (SMEs). His findings recommend that during truth oblique regulate varieties resembling body of workers recruiting techniques and cultural components have a better functionality influence than conventional keep an eye on types similar to budgeting or approach reports.

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

Sample text

Fi (a), . . , fj (a), . . , fn (a)) element uniqueness geh¨ ort dann aber nicht zur Menge W . 5. ✷ Ganz analog l¨aßt sich ein ¨ahnliches Problem behandeln, das den Namen element uniqueness tr¨agt. Gegeben sind wieder n reelle Zahlen x1 , . . , xn , gefragt ist, ob es Indizes i = j mit xi = xj gibt. 8 Sortieren, z. B. mit Heapsort, ben¨ otigt nur Vergleiche. Tests der Art xi − xj − ε < 0 sind im linearen Modell erlaubt. 7 Das Problem element uniqueness hat die Zeitkomplexit¨at Θ(n log n) im linearen Modell.

In diesem Buch werden ausschließlich sequentielle Algorithmen betrachtet. 2 Ein paar Grundbegriffe mischen Geometrie interessiert, sei z. B. auf Dehne und Sack [40] verwiesen. 5 Untere Schranken Ein Problem hat die Zeitkomplexit¨at Ω(f ), wenn es f¨ ur jeden Algorithmus eine Konstante c > 0 gibt, so daß sich f¨ ur jedes hinreichend große n Beispiele der Gr¨oße n finden lassen, f¨ ur deren L¨ osung der Algorithmus mindestens cf (n) viele Schritte ben¨otigt. Die Funktion f heißt dann eine untere Schranke f¨ ur das Problem.

Die naive Berechnung der maximalen Teilsumme f¨ uhrt zu einem Algorithmus mit drei geschachtelten for-Schleifen f¨ ur i, j und einen Summationsindex k; seine Laufzeit ist in Θ(n3 ).

Download PDF sample

Rated 4.89 of 5 – based on 34 votes