|
|
 |
|
Viewing report
|
|
|
|
Optimal Area Triangulation. Edition No. 1
VDM Publishing House, April 2009, Pages: 136
Triangulations of point sets play an important role
in Computational Geometry and have been studied
extensively in the last decades. The results on
optimizing angles and edge lengths are classical in
the field. Here we present a study on optimizing the
area in two ways: minimizing the maximum area of a
triangle, and maximizing the minimum area of a
triangle. In the case of a point set in convex
position we present nearly quadratic algorithms for
both problems. The geometric properties of these two
optimal triangulations are derived and extensively
discussed. We strongly believe that both problems
admit no worse than quadratic solution. Such will be
based on a refinement of the geometric properties.
Furthermore, the properties and the methods
described here can serve as a starting point to
obtaining efficient optimal triangulation algorithms
for other quality measures such as maximizing
inradius or aspect ratio of a triangle. In the case
of a point set in general position, we present a
polynomial time approximation algorithm. The
algorithm is based on the matching properties of
triangulations and further geometric considerations.
|
|
|
|
