Kompatible Triangulierungen ebener Punktmengen
Abstract:
Triangulations are very important in computational geometry, since a lot of
algorithms make use of this data structure. The subject of this thesis is the
special problem of compatible triangulations. The original motivation to
investigate this problem comes from cartography. Two point sets in the plane
are called compatible if isomorphic triangulations exist. First the structure
of the convex hulls of compatible triangulations is analyzed in the case of
edge-compatibility. Then it is shown that triangle-compatibility simplifies
the situation. A connection to lambda-matrices is also given. If two point
sets have the same lambda-matrices then every triangulation of one point set
admits a compatible triangulation of the other point set. At last the main
conjecture on compatible triangulations, namely that every two point sets of
same cardinality in general position that have an identical number of points
on the convex hulls admit compatible triangulations, is proved for some
special cases.
Reference: H. Krasser.
Kompatible triangulierungen ebener punktmengen.
Master's thesis, Institute for Theoretical Computer Science, Graz University
of Technology, Austria, June 1999.
(in German).