General analysis tool box for controlled perturbation algorithms and complexity and computation of Θ-guarded regions

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.