论文标题
在多面体球体上找到弱简单的封闭的quasigeodesics
Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres
论文作者
论文摘要
凸多面体上的封闭的quasigeodesic是一条封闭的曲线，在顶点外部局部笔直，在该曲线上，它在两侧最多形成一个$π$的角度。虽然Pogorelov在1949年证明了在凸多面体上的简单封闭式Quasigeodesic的存在，但找到了一种多项式时算法来计算这种简单的封闭的准式质量，已反复出现是一个开放的问题。我们的第一个贡献是在（不一定是凸）多面体球体的内在环境中提出对准化学的扩展定义，并在这种情况下证明存在弱简单的封闭的quasigeodesic。我们的证明不是通过平滑表面的近似值进行的，而是依赖于Hass和Scott的磁盘流与多面体表面的背景的适应。我们的第二个结果是利用该存在定理提供有限的算法来计算多面体球上的弱简单的封闭式准二核。在凸多面体上，我们的算法计算了一个简单的封闭的准胶质，解决了Demaine，Herssterberg和Ku的开放问题。
A closed quasigeodesic on a convex polyhedron is a closed curve that is locally straight outside of the vertices, where it forms an angle at most $π$ on both sides. While the existence of a simple closed quasigeodesic on a convex polyhedron has been proved by Pogorelov in 1949, finding a polynomial-time algorithm to compute such a simple closed quasigeodesic has been repeatedly posed as an open problem. Our first contribution is to propose an extended definition of quasigeodesics in the intrinsic setting of (not necessarily convex) polyhedral spheres, and to prove the existence of a weakly simple closed quasigeodesic in such a setting. Our proof does not proceed via an approximation by smooth surfaces, but relies on an adapation of the disk flow of Hass and Scott to the context of polyhedral surfaces. Our second result is to leverage this existence theorem to provide a finite algorithm to compute a weakly simple closed quasigeodesic on a polyhedral sphere. On a convex polyhedron, our algorithm computes a simple closed quasigeodesic, solving an open problem of Demaine, Hersterberg and Ku.
