Please use this identifier to cite or link to this item: doi:10.22028/D291-25697
Title: Combinatorial curve reconstruction and the efficient exact implementation of geometric algorithms
Other Titles: Kombinatorische Kurvenrekonstruktion und die exakte und effiziente Implementierung von Geometrischen Algorithmen
Author(s): Funke, Stefan
Language: English
Year of Publication: 2001
SWD key words: Stichprobe ; Punktmenge ; Kurve ; Rekonstruktion ; Polynomialzeitalgorithmus
Free key words: Algorithmische Geometrie
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
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.
Link to this record: urn:nbn:de:bsz:291-scidok-1830
hdl:20.500.11880/25753
http://dx.doi.org/10.22028/D291-25697
Advisor: Kurt Mehlhorn
Date of oral examination: 30-Jul-2001
Date of registration: 1-Apr-2004
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 
StefanFunke_ProfDrKurtMehlhorn.pdf820,91 kBAdobe PDFView/Open


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