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

Mirzoev, Tigran; Vassilev, Tzvetalin

Serdica Journal of Computing (2010)

- Volume: 4, Issue: 3, page 335-348
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topMirzoev, Tigran, and Vassilev, Tzvetalin. "Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons." Serdica Journal of Computing 4.3 (2010): 335-348. <http://eudml.org/doc/11393>.

@article{Mirzoev2010,

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

author = {Mirzoev, Tigran, Vassilev, Tzvetalin},

journal = {Serdica Journal of Computing},

keywords = {Computational Geometry; Triangulation; Convex Polygon; Dynamic Programming; computational geometry; triangulation; convex polygon; dynamic programming},

language = {eng},

number = {3},

pages = {335-348},

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

title = {Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons},

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

volume = {4},

year = {2010},

}

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

PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences

VL - 4

IS - 3

SP - 335

EP - 348

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

LA - eng

KW - Computational Geometry; Triangulation; Convex Polygon; Dynamic Programming; computational geometry; triangulation; convex polygon; dynamic programming

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

ER -

## NotesEmbed ?

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