Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/1598

 Title: Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints Authors: Mark Keil, JVassilev, Tzvetalin Keywords: Computational GeometryTriangulationPlanar Point SetAngle Restricted TriangulationApproximationDelauney Triangulation Issue Date: 2010 Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences Citation: Serdica Journal of Computing, Vol. 4, No 3, (2010), 321p-334p Abstract: 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 Description: * A preliminary version of this paper was presented at XI Encuentros de Geometr´ia Computacional, Santander, Spain, June 2005. URI: http://hdl.handle.net/10525/1598 ISSN: 1312-6555 Appears in Collections: Volume 4 Number 3

Files in This Item:

File Description SizeFormat