Combinatorial curve reconstruction and the efficient exact implementation of geometric algorithms

摘要

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.