BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2010 >
Volume 4 Number 3 >

Please use this identifier to cite or link to this item:

Title: Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons
Authors: Mirzoev, Tigran
Vassilev, Tzvetalin
Keywords: Computational Geometry
Convex Polygon
Dynamic Programming
Issue Date: 2010
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 4, No 3, (2010), 335p-348p
Abstract: 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.
ISSN: 1312-6555
Appears in Collections:Volume 4 Number 3

Files in This Item:

File Description SizeFormat
sjc126-vol4-num3-2010.pdf223.98 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License