Optimal Area Triangulation
of Planar Point Sets
Versandkostenfrei!
Versandfertig in 6-10 Tagen
38,99 €
inkl. MwSt.
PAYBACK Punkte
19 °P sammeln!
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 probl...
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.
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.
Andere Kunden interessierten sich für
