Please use this identifier to cite or link to this item: doi:10.22028/D291-26536
Title: General analysis tool box for controlled perturbation algorithms and complexity and computation of Θ-guarded regions
Author(s): Osbild, Ralf
Language: English
Year of Publication: 2012
SWD key words: Algorithmische Geometrie
Kombinatorische Geometrie
Analyse
Free key words: computational geometry
controlled perturbation
Θ-guarded region
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: This thesis belongs to the field of computational geometry and addresses the following two issues. 1. The implementation of reliable and efficient geometric algorithms is a challenging task. Controlled perturbation combines the speed of floating-point arithmetic with a mechanism that guarantees reliability. We present a general tool box for the analysis of controlled perturbation algorithms. This tool box is separated into independent components. We present three alternative approaches for the derivation of the most important bounds. Furthermore, we have included polynomial-based predicates, rational function-based predicates, and object-preserving perturbations into the theory. Moreover, the tool box is designed such that it reflects the actual behavior of the algorithm at hand without simplifying assumptions. 2. Illumination and guarding problems are a wide field in computational and combinatorial geometry to which we contribute the complexity and computation of Θ-guarded regions. They are a generalization of the convex hull and are related to α-hulls and Θ-maxima. The difficulty in the study of Θ-guarded regions is the dependency of its shape and complexity on Θ. For all angles Θ, we prove fundamental properties of the region, derive lower and upper bounds on its worst-case complexity, and present an algorithm to compute the region.
Diese Dissertation auf dem Gebiet der Algorithmischen Geometrie beschäftigt sich mit den folgenden zwei Problemen. 1. Die Implementierung von verlässlichen und effizienten geometrischen Algorithmen ist eine herausfordernde Aufgabe. Controlled Perturbation verknüpft die Geschwindigkeit von Fließkomma-Arithmetik mit einem Mechanismus, der die Verlässlichkeit garantiert. Wir präsentieren einen allgemeinen ,,Werkzeugkasten” zum Analysieren von Controlled Perturbation Algorithmen. Dieser Werkzeugkasten ist in unabhängige Komponenten aufgeteilt. Wir präsentieren drei alternative Methoden für die Herleitung der wichtigsten Schranken. Des Weiteren haben wir alle Prädikate, die auf Polynomen und rationalen Funktionen beruhen, sowie Objekt-erhaltende Perturbationen in die Theorie miteinbezogen. Darüber hinaus wurde der Werkzeugkasten so entworfen, dass er das tatsächliche Verhalten des untersuchten Algorithmus ohne vereinfachende Annahmen widerspiegelt. 2. Illumination und Guarding Probleme stellen ein breites Gebiet der Algorithmischen und Kombinatorischen Geometrie dar. Hierzu tragen wir die Komplexität und Berechnung von Θ-bewachten Regionen bei. Sie stellen eine Verallgemeinerung der konvexen Hülle dar und sind mit α-hulls und Θ-maxima verwandt. Die Schwierigkeit beim Studium der Θ-bewachten Regionen ist die Abhängigkeit ihrer Form und Komplexität von Θ. Für alle Winkel Θ beweisen wir grundlegende Eigenschaften der Region, leiten untere und obere Schranken ihrer worst-case Komplexität her und präsentieren einen Algorithmus, um die Region zu berechnen.
Link to this record: urn:nbn:de:bsz:291-scidok-55201
hdl:20.500.11880/26592
http://dx.doi.org/10.22028/D291-26536
Advisor: Mehlhorn, Kurt
Date of oral examination: 2-Aug-2013
Date of registration: 30-Sep-2013
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_Ralf_Osbild.pdf978,46 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.