DECOMPOSING A POLYGON INTO SIMPLER COMPONENTS
DECOMPOSING A POLYGON INTO SIMPLER COMPONENTS
复制标题
DOI：
10.1137/0214056
复制
发表时间：
1985-01-01
影响因子：
1.6
通讯作者：
KEIL, JM
中科院分区：
文献类型：
--
作者：
KEIL, JM
将一个多边形分解成更简单的分量是计算几何、句法模式识别和图形学等领域感兴趣的问题。本文考虑不引入Steiner点的分解。我们考虑的较简单的组件是凸多边形、螺旋多边形、星形多边形和单调多边形。我们应用了一种提高动态规划算法效率的技术，以实现将一个简单的多边形分解成每种分量类型的最小数目的问题的多项式时间算法。使用相同的技术，我们能够展示多项式时间算法，用于将简单的多边形分解成每种组件类型的问题，同时最小化用于形成分解的内部边的长度。当多边形被允许包含孔洞时，许多问题就变成了NP难的。
The problem of decomposing a polygon into simpler components is of interest in fields such as computational geometry, syntactic pattern recognition, and graphics. In this paper we consider decompositions which do not introduce Steiner points. The simpler components we consider are convex polygons, spiral polygons, star-shaped polygons and monotone polygons. We apply a technique for improving the efficiency of dynamic programming algorithms in order to achieve polynomial time algorithms for the problems of decomposing a simple polygon into the minimum number of each of the component types. Using the same technique we are able to exhibit polynomial time algorithms for the problems of decomposing a simple polygon into each of the component types while minimizing the length of the internal edges used to form the decomposition. When the polygons are allowed to contain holes many of the problems become NP-hard.