Geodesic
Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints
Serdica Journal of Computing, Tome 4 (2010) no. 3, pp. 321-334 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

We consider sets of points in the two-dimensional Euclidean plane. For a planar point set in general position, i.e. no three points collinear, a triangulation is a maximal set of non-intersecting straight line segments with vertices in the given points. These segments, called edges, subdivide the convex hull of the set into triangular regions called faces or simply triangles. We study two triangulations that optimize the area of the individual triangles: MaxMin and MinMax area triangulation. MaxMin area triangulation is the triangulation that maximizes the area of the smallest area triangle in the triangulation over all possible triangulations of the given point set. Similarly, MinMax area triangulation is the one that minimizes the area of the largest area triangle over all possible triangulations of the point set. For a point set in convex position there are O(n^2 log n) time and O(n^2) space algorithms that compute these two optimal area triangulations. No polynomial time algorithm is known for the general case. In this paper we present an approach
Keywords: Computational Geometry, Triangulation, Planar Point Set, Angle Restricted Triangulation, Approximation, Delauney Triangulation 
@article{SJC_2010_4_3_a3,
     author = {Mark Keil, J and Vassilev, Tzvetalin},
     title = {Approximating the {MaxMin} and {MinMax} {Area} {Triangulations} using {Angular} {Constraints}},
     journal = {Serdica Journal of Computing},
     pages = {321--334},
     year = {2010},
     volume = {4},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a3/}
}
TY  - JOUR
AU  - Mark Keil, J
AU  - Vassilev, Tzvetalin
TI  - Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints
JO  - Serdica Journal of Computing
PY  - 2010
SP  - 321
EP  - 334
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a3/
LA  - en
ID  - SJC_2010_4_3_a3
ER  - 
%0 Journal Article
%A Mark Keil, J
%A Vassilev, Tzvetalin
%T Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints
%J Serdica Journal of Computing
%D 2010
%P 321-334
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a3/
%G en
%F SJC_2010_4_3_a3
Mark Keil, J; Vassilev, Tzvetalin. Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints. Serdica Journal of Computing, Tome 4 (2010) no. 3, pp. 321-334. http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a3/