|
| S09205 Computational Geometry |
During the first three years of this NFN we have been able to obtain a
huge variety of results for the different proposed activities. We
obtained several structural and algorithmic results on
pseudo-triangulations and their modifications to more general face
shape and to higher dimensions. The concept of pseudo-triangulations
has been generalized to geometric graphs, enabling us to obtain new
results on optimizing and presenting several classes of geometric
graphs. This includes questions from graph drawing, enumeration, and
also Ramsey-type results.
In the context of advanced geometric representations the synergies of
approximation theory and computational geometry are studied. We
considered the trade-off between the usage of (a huge number of)
simple objects like points and straight lines allowing simple
operations on the one hand and (a smaller number of) more complex
objects like splines and nurbs requiring more involved operations. Our
results show that this indeed leads to algorithms with improved 'real
world' complexity.
Moreover using spheres and Voronoi diagrams we have been able to
represent complex geometric objects with easy to handle primitives. In
particular by approximating 3D objects with spheres we obtained
efficient methods to compute the Minkowski-sum of non-convex objects
and the developement of a new way to compute the medial axis in a
reliable and stable way is a promising task.
Results have been obtained in the following areas:
- Triangulations, pseudo-triangulations and relatives
- Spheres and Voronoi diagrams
- Geometric graphs
- Advanced geometric representations
A detailed report of the first funding period is available here. See also the list of Publications.
Fig. 1: Dragon for different tolerances
 |  |  |
| a) | b) | c) |
| | | | | |
| |
Fig. 2: (a) Polygonal workspace approximated (b) with 57 circles and
tolerance 1% (of size of bounding box) and (c) with 117 circles and
tolerance 0.1%
| |
| 
