Astrid Sturm

Geometric Approximations in Two- and Three Dimensional Space

Betreuer: Prof. Dr. Günter Rote
Abschluss: PhD
Abgabedatum: 27.11.2009
Homepage des Autors:


The goal of geometric approximation is to replace a given complex geometric object by a simpler object while capturing the significant features of the original. 
In the first part of the thesis we deal with approximating polygonal curves in 2-dimensional space. For a polygonal curve this approximation can be done either by a simpler polygonal curve (a curve with less segments) or by a higher order curve. We were able to compute an approximation of open polygonal curves with the minimum number of circular arcs (chapter 1) and also with the minimum number of biarcs (chapter 2) for a given upper error bound epsilon. 
In the second part of the thesis we move on the 3-dimensional space and to polytope approximations. 
We initiate the study of this problem by considering convex surfaces only, for simplicity, before moving on to non convex surfaces. 
A first natural step to higher order approximation of convex polytopes is the approximation with spheres or spherical patches. 
In chapter 3 we can show that deciding the existence of an approximation of a convex polytope with a given upper error bound epsilon and not more than a given number of spherical patches is NP-hard. 
In chapter 4 we present a new technique for constructing a curved surfaces based on inscribed polytopes resulting in a convex surface consisting of spherical patches. 
To tackle the approximation problem for non-convex polytopes we pick up the idea of an incremental approximation algorithm introduced in chapter 4. This induces the problem of finding a simple and topological correct start polytope, the seed polytope, for non-convex polytopes. 
In chapter 5 we describe how to construct for a surface in 3D space, given by sample points S, a coarse approximating polytope P that uses a subset of the points as vertices and preserves the topology. In contrast to surface reconstruction we do not use all sample points, but we try to use as few points as possible. 
We also give a short introduction how to use the results for the seed polytope generation for surface reconstruction.