Geodesic
Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons
Serdica Journal of Computing, Tome 4 (2010) no. 3, pp. 335-348 Cet article a éte moissonné depuis la source Bulgarian Digital Mathematics Library

Voir la notice de l'article

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.
Keywords: Computational Geometry, Triangulation, Convex Polygon, Dynamic Programming 
@article{SJC_2010_4_3_a4,
     author = {Mirzoev, Tigran and Vassilev, Tzvetalin},
     title = {Quadratic {Time} {Computable} {Instances} of {MaxMin} and {MinMax} {Area} {Triangulations} of {Convex} {Polygons}},
     journal = {Serdica Journal of Computing},
     pages = {335--348},
     year = {2010},
     volume = {4},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a4/}
}
TY  - JOUR
AU  - Mirzoev, Tigran
AU  - Vassilev, Tzvetalin
TI  - Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons
JO  - Serdica Journal of Computing
PY  - 2010
SP  - 335
EP  - 348
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a4/
LA  - en
ID  - SJC_2010_4_3_a4
ER  - 
%0 Journal Article
%A Mirzoev, Tigran
%A Vassilev, Tzvetalin
%T Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons
%J Serdica Journal of Computing
%D 2010
%P 335-348
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a4/
%G en
%F SJC_2010_4_3_a4
Mirzoev, Tigran; Vassilev, Tzvetalin. Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons. Serdica Journal of Computing, Tome 4 (2010) no. 3, pp. 335-348. http://geodesic.mathdoc.fr/item/SJC_2010_4_3_a4/