Optimal Triangulation with Steiner Points
Optimal Triangulation with Steiner Points
复制标题
DOI：
10.1007/978-3-540-77120-3_59
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
B. Aronov;T. Asano;S. Funke
中科院分区：
文献类型：
--
作者：
B. Aronov;T. Asano;S. Funke
对简单多边形进行三角剖分有很多种方法；对于某些优化准则，如最小内角最大化，如何根据该准则有效地计算最佳三角剖分是已知的。在本文中，我们考虑了这个问题的一个自然扩展：给定一个简单的多边形p和一个斯坦纳点在其内部，确定p的最优位置和p的所有三角剖分和放置中最好的三角形剖分p。当优化准则为最小角度最大化时，给出了求解该问题的多项式时间算法。此外，我们还提供了一个更一般的多项式时间算法，用于在相同的优化准则下寻找常数个数的斯坦纳点的最优位置。
There are many ways to triangulate a simplen-gon; for certain optimization criteria such as maximization of the smallest internal angle it is known how to efficiently compute the best triangulation with respect to this criterion. In this paper we consider a natural extension of this problem: Given a simple polygonPand one Steiner pointpin its interior, determine the optimal location ofpand a triangulation ofPandpwhich is best amongst all triangulations and placements ofp. We present a polynomial-time algorithm for this problem when the optimization criterion is maximization of the minimum angle. Furthermore, we also provide a more general polynomial-time algorithm for finding the optimal placement of a constant number of Steiner points under the same optimization criterion.