# Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints

Mark Keil, J; Vassilev, Tzvetalin

Serdica Journal of Computing (2010)

- Volume: 4, Issue: 3, page 321-334
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topMark Keil, J, and Vassilev, Tzvetalin. "Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints." Serdica Journal of Computing 4.3 (2010): 321-334. <http://eudml.org/doc/11392>.

@article{MarkKeil2010,

abstract = {* 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 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},

author = {Mark Keil, J, Vassilev, Tzvetalin},

journal = {Serdica Journal of Computing},

keywords = {Computational Geometry; Triangulation; Planar Point Set; Angle Restricted Triangulation; Approximation; Delauney Triangulation; computational geometry; triangulation; planar point set; angle restricted triangulation; approximation; Delauney triangulation; MinMax area triangulation; MaxMin area triangulation; algorithms},

language = {eng},

number = {3},

pages = {321-334},

publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},

title = {Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints},

url = {http://eudml.org/doc/11392},

volume = {4},

year = {2010},

}

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

PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences

VL - 4

IS - 3

SP - 321

EP - 334

AB - * 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 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

LA - eng

KW - Computational Geometry; Triangulation; Planar Point Set; Angle Restricted Triangulation; Approximation; Delauney Triangulation; computational geometry; triangulation; planar point set; angle restricted triangulation; approximation; Delauney triangulation; MinMax area triangulation; MaxMin area triangulation; algorithms

UR - http://eudml.org/doc/11392

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.