Topologically Consistent Algorithms Realted to Convex Polyhedra
Topologically Consistent Algorithms Realted to Convex Polyhedra
复制标题
凸多面体的拓扑一致算法
DOI：
10.1007/3-540-56279-6_74
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
K. Sugihara
中科院分区：
文献类型：
--
作者：
K. Sugihara
本文提出了一种设计三维空间中凸多面体的数值稳健且拓扑一致的几何算法的通用方法。当且仅当图是平面且三重连通时，图才是凸多面体的点边图（斯坦尼茨定理）。在此定理的基础上，对传统的几何算法进行了修改，使得无论数值计算的精度多么差，输出的图至少是平面的、三连通的。由此产生的算法在有限精度算术中不会失败的意义上是鲁棒的，并且在输出是扰动输入的真实解的意义上是一致的。
The paper presents a general method for the design of numerically robust and topologically consistent geometric algorithms concerning convex polyhedra in the three-dimensional space. A graph is the vertex-edge graph of a convex polyhedron if and only if it is planar and triply connected (Steinitz' theorem). On the basis of this theorem, conventional geometric algorithms are revised in such a way that, no matter how poor the precision in numerical computation may be, the output graph is at least planar and triply connected. The resultant algorithms are robust in the sense that they do not fail in finiteprecision arithmetic, and are consistent in the sense that the output is the true solution to a perturbed input.