Ph.D. thesis : Geometric Approximations in Two- and Three Dimensional Space
Advisor: Prof. Dr. Günter Rote
(Im Rahmen des Projektes: ECG, Effective Computational Geometry for Curves and Surfaces.)
In this thesis we study approximation problems for curves and surfaces.
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. If the original object is given by a set of sample points, this problem is also called reconstruction. Approximating and reconstructing objects is a problem that arises in many applications such as computer graphics, computer vision, medical imaging and cartography, to name only a few. The problem goes back decades and is one of the major challenges in computational geometry.
For a polygonal curve an approximation can be done either by a simpler polygonal (curve a curve with less segments) or by a higher order curve.
The approximation of polygonal curves is a wide topic and many results have already been presented in the past.
There is a wide range of publications on the approximation of polygonal curves or ordered set of points by polygonal curves, for example, the publications of Imai and Iri, or Guibas and Hershberger, to mention only a few.
As some optimization problems were answered for polygonal approximation,
the same questions arise for approximation with curves of higher order.
The approximation of polygonal curves with curves of higher order, especially with arcs and biarcs, has been mostly heuristic.
Higher-order approximations of polygonal curves come into place in areas as, e.g., computer-aided manufacturing environments, geometric modeling and robot path planing. One major task is to smooth the path of, e.g., cutting machines or robots.
For example in computer-aided manufacturing environments, tool paths are
usually made of line segments and circular arcs, see Mekk and Walton.
Now the question of how to approximate polygonal curves with circular arcs or biarcs with certain guarantees arises.
We were able to answer the min-# problem for approximating open polygonal curves with circular arcs and also for biarcs.
The approximation of surfaces and, especially, the reconstruction from scattered data points has received a lot of attention in the past. The problem of reconstructing a surface from a set of sample points is ill-posed by nature. Without certain constraints the given point cloud can be interpolated by infinitely many shapes with differing topology.
The notion of a sufficiently dense sample, the r-sample, introduced by Amenta and Bern, introduces a constraint on the input data set. With this constraint the corresponding set of reconstructible shapes have all the same topology type as the surface.
A large range of algorithms are based on the r-sample theory.
The Delaunay triangulation of the input point set plays another major role in all of these methods, as it does in the alpha-shape theory of Edelsbrunner.
Our approach to surface reconstruction, which is similar to the work of Chazal and Lieutier, is also based on Delaunay triangulation of the input point set, and we require that the sampling is an r-sample.
We construct an approximating polytope P that uses a subset of the
input sample points as its vertices and preserves the topology of the sampled surface.
Our goal is, on the one hand, to use as few points of the input set as possible and, on the other,
to get a flexible approximation with a level of detail that can be tuned from coarse to fine.
Using a tailored technique of pruning the surface balls, we obtain a
coarse-to-fine approximation of the surface by polytopes.
This is the
first result that uses, from a practical point of view, approximations of local feature size
and medial axis to obtain locally adaptive reconstructions of an unknown surface.