Displaying similar documents to “On the area discrepancy of triangulations of squares and trapezoids.”

Distinct equilateral triangle dissections of convex regions

Diane M. Donovan, James G. Lefevre, Thomas A. McCourt, Nicholas J. Cavenagh (2012)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We define a proper triangulation to be a dissection of an integer sided equilateral triangle into smaller, integer sided equilateral triangles such that no point is the vertex of more than three of the smaller triangles. In this paper we establish necessary and sufficient conditions for a proper triangulation of a convex region to exist. Moreover we establish precisely when at least two such equilateral triangle dissections exist. We also provide necessary and sufficient conditions for...

Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints

Mark Keil, J, Vassilev, Tzvetalin (2010)

Serdica Journal of Computing

Similarity:

* A preliminary version of this paper was presented at XI Encuentros de Geometr´ia Computacional, Santander, Spain, June 2005. 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...

Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

Mirzoev, Tigran, Vassilev, Tzvetalin (2010)

Serdica Journal of Computing

Similarity:

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...