Algorithms for optimal area triangulations of a convex polygon

被引:12
作者
Keil, J. Mark
Vassilev, Tzvetalin S.
机构
[1] Univ Saskatchewan, Dept Comp Sci, Saskatoon, SK S7N 5C9, Canada
[2] N Carolina Cent Univ, Dept Math & Comp Sci, Durham, NC 27707 USA
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2006年 / 35卷 / 03期
基金
加拿大自然科学与工程研究理事会;
关键词
triangulations; convex polygons; dynamic programming;
D O I
10.1016/j.comgeo.2006.03.004
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of nonintersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n(2) log n) time and O(n(2)) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码:173 / 187
页数:15
相关论文
共 50 条
[41]   Optimal receiver scheduling algorithms for a multicast problem [J].
Bertossi, A. A. ;
Pinotti, M. C. ;
Rizzi, R. .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (15) :3187-3197
[42]   Algorithms for optimal multi-resolution quantization [J].
Dumitrescu, S ;
Wu, XL .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 50 (01) :1-22
[43]   On optimal multiple changepoint algorithms for large data [J].
Maidstone, Robert ;
Hocking, Toby ;
Rigaill, Guillem ;
Fearnhead, Paul .
STATISTICS AND COMPUTING, 2017, 27 (02) :519-533
[44]   AREA TIME OPTIMAL ADDER DESIGN [J].
WEI, BWY ;
THOMPSON, CD .
IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (05) :666-675
[46]   Existence of solutions in non-convex dynamic programming and optimal investment [J].
Teemu Pennanen ;
Ari-Pekka Perkkiö ;
Miklós Rásonyi .
Mathematics and Financial Economics, 2017, 11 :173-188
[47]   Existence of solutions in non-convex dynamic programming and optimal investment [J].
Pennanen, Teemu ;
Perkkioe, Ari-Pekka ;
Rasonyi, Miklos .
MATHEMATICS AND FINANCIAL ECONOMICS, 2017, 11 (02) :173-188
[48]   AN OPTIMAL ALGORITHM WITH UNKNOWN TIME-COMPLEXITY FOR CONVEX MATRIX SEARCHING [J].
LARMORE, LL .
INFORMATION PROCESSING LETTERS, 1990, 36 (03) :147-151
[49]   Algorithms for computing numerical optimal feedback motion strategies [J].
LaValle, SM ;
Konkimalla, P .
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2001, 20 (09) :729-752
[50]   Optimal algorithms for recovery point insertion in recoverable microarchitectures [J].
Blough, DM ;
Kurdahi, FJ ;
Ohm, SY .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1997, 16 (09) :945-955