闭合准生是多面体表面的闭合曲线,所有点上两面最多180^∘;这种曲线可以直接局部展开。 1949年,Pogorelov证明每个凸多面体至少有三个(非自相交)闭合的准词法,但证明依赖于非建设性的拓扑论证。 我们提出了第一个有限算法,在给定的凸多面体上找到一个闭合的准词位,这是O'Rourke和Wyman在1990年开放问题上的第一个积极进展。 该算法还在对人脸(线段数)的访问总数上建立了伪多项式上限,即O(n L^2/ε^2 l^2)其中n是多面体顶点数,ε是顶点的最小曲率,L是最长边缘的长度,l是顶点与非事件边缘(最小特征大小)之间的最小距离。 在真正的RAM上,算法的运行时间也是伪多项式,即 O(L^2/ε^2 l^2 n n)。 在一个单词RAM上,运行时间增长到O(b^2 Δ^36 L^146/ε^98 l^146 n n · 2^O(|R|)),其中Δ≤n是多面体的最大顶点度,假设多面体的内在几何体是由具有b位整数的恒定大小的激进表达式给出的,并且最多 |R| 是不同的平方根。 在此过程中,我们引入了计算的表达式RAM模型,将过去精确几何计算工作所暗示的真实RAM和单词RAM之间的联系正式化。