Convex decompositions of polyhedra
Convex decompositions of polyhedra
复制标题
多面体的凸分解
DOI：
--
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
B. Chazelle
中科院分区：
文献类型：
--
作者：
B. Chazelle
计算几何的一个重要研究方向是寻找将复杂结构分解为简单组件的方法。在本文中，我们研究的问题分解成一个三维多面体P的凸片的最小数目。设n是P中的顶点数，N是具有反射角的边数（即P的凹口），我们的主要结果是计算P的凸分解的O（N3）时间算法。该算法产生O（N2）凸部分，这在最坏情况下是最优的。在大多数出现问题的情况下（例如图形，工具设计，模式识别），凹口的数量N似乎在很大程度上取决于顶点的数量n;因此该算法在实践中是可行的。
An important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. In this paper, we examine the problem of decomposing a three-dimensional polyhedron P into a minimal number of convex pieces. Letting n be the number of vertices in P and N the number of edges which exhibit a reflex angle (i.e. the notches of P), our main result is an O(nN3) time algorithm for computing a convex decomposition of P. The algorithm produces O(N2) convex parts, which is optimal in the worst case. In most situations where the problem arises (e.g. graphics, tool design, pattern recognition), the number of notches N seems greatly dominated by the number of vertices n; the algorithm is therefore viable in practice.