Kurvenrekonstruktion und die effiziente exakte Implementierung geometrischer Algorithmen

sich mit dem Problem 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\"asentieren einen kombinatorischen Algorithmus, der das
Kurvenrekonstruktionsproblem in polynomieller Zeit l\"ost. Es ist der
erste Algorithmus, der beweisbar Mengen von Kurven rekonstruieren kann,
wenn diese auch Ecken und Endpunkte beinhalten d\"urfen.

Der zweite Teil dieser Dissertation handelt von der exakten und effizienten
Implementierung von Geometrischen Algorithmen. Wir entwickeln zun\"achst ein
generalisiertes Filterschema, um exakte geometrische Berechnungen zu
beschleunigen, und entwerfen dann das Design eines objektorientierten Kernels
f\"ur geometrische Berechnungen.