Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25697
Titel: Combinatorial curve reconstruction and the efficient exact implementation of geometric algorithms
Sonstige Titel: Kombinatorische Kurvenrekonstruktion und die exakte und effiziente Implementierung von Geometrischen Algorithmen
Verfasser: Funke, Stefan
Sprache: Englisch
Erscheinungsjahr: 2001
SWD-Schlagwörter: Stichprobe ; Punktmenge ; Kurve ; Rekonstruktion ; Polynomialzeitalgorithmus
Freie Schlagwörter: Algorithmische Geometrie
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: 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 zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-1830
hdl:20.500.11880/25753
http://dx.doi.org/10.22028/D291-25697
Erstgutachter: Kurt Mehlhorn
Tag der mündlichen Prüfung: 30-Jul-2001
SciDok-Publikation: 1-Apr-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
StefanFunke_ProfDrKurtMehlhorn.pdf820,91 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.