Combinatorial curve reconstruction and the efficient exact implementation of geometric algorithms

Abstract

This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Gamma, the task is to compute the graph G(S, Gamma) which has vertex set S and an edge between exactly those pairs of vertices that are adjacent on some curve in Gamma. We present a purely combinatorial algorithm that solves the curve reconstruction problem in polynomial time. It is the first algorithm which provably handles collections of curves with corners and endpoints. In the second part of this thesis, we will be concerned with the exact and efficient im plementation of geometric algorithms. First, we develop a generalized filtering scheme to speed-up exact geometric computation and then discuss the design of an object-oriented kernel for geometric computation.

Diese Dissertation besteht aus zwei Teilen. Der erste Teil beschäftigt sich mit den Problemen der Kurvenrekonstruktion. Gegeben eine endliche Menge von Stichprobenpunkten S von einer Menge von unbekannten Kurven Gamma, besteht die Aufgabe darin, den Graphen G(S, Gamma) zu konstruieren, welcher die Knotenmenge S und Kanten zwischen genau den Knotenpaaren besitzt, welche auf einer der Kurven in Gamma adjazent sind. Wir präsentieren einen rein kombinatorischen Algorithmus, der das Kurevenkonstruktionsproblem in polynomieller Zeit löst. Es ist der erste Algorithmus, der beweisbar Mengen von Kurven rekonstruieren kann, wenn diese auch Ecken und Endpunkte beinhalten dürfen. Der zweite Teil dieser Dissertation handelt von der exakten und effizienten Implementierung von Geometrischen Algorithmen. Wir entwickeln zunächst ein generalisiertes Filterschema, um exakte geometrische Berechnungen zu beschleunigen, und entwerfen dann das Design eines objektorientierten Kernels für geometrische Berechnungen.