论文标题
在凸Polyhedra上查找封闭的quasigeodesics
Finding Closed Quasigeodesics on Convex Polyhedra
论文作者
论文摘要
封闭的quasigeodesic是多面体表面上的封闭曲线，两侧的表面上最多为$ 180^\ circ $；这样的曲线可以局部直截了当。 1949年，Pogorelov证明了每个凸多面体至少具有三个（非换隔离）封闭的准胶质学，但证据依赖于非构造性拓扑论点。我们提出了第一个有限算法，可以在给定的凸多面体上找到封闭的quasigeodesic，这是O'Rourke和Wyman在1990年开放问题上的第一个积极进步。该算法首次建立了对面对面的访问总数（线段数）的总数，即$ o \ left（\ frac {n \，l^3} {am^2 \，\ ell^3} \ ell^3} \ right）$ n是$ n是$ n是$ n是$ n $ curne $ curne $ curhed curhed curhed a curhed curhe a curhed curhed curhe curhe curhe the顶点，$ l $是最长边缘的长度，而$ \ ell $是顶点和非固定边缘之间的面部最小距离（任何面部的最小特征大小）。在真实的RAM上，算法的运行时间也是pseudopolynomial，即$ o \ left（\ frac {n \，l^3} {ε^2 \，\ ell^3} \ log n \ n \ right）$。在单词ram上，运行时间生长到$ o \ left（b^2 \ cdot \ frac {n^8 \ log n} {ε^8} \ cdot \ frac \ frac {l^{21}}} {\ ell^{\ ell^{21}}}}}}}} \ cdot 2^{o（假设多面体的固有或外在几何形状是由最多与$ b $ bit的每个坐标给出的。这段时间绑定仍然是Polyhedra的假popolynomial，具有$ O（\ log n）$不同的边缘长度，但在最坏情况下是指数级。在此过程中，我们介绍了计算的表达式RAM模型，并在过去的精确几何计算上的工作暗示了真实RAM和单词RAM之间的联系。
A closed quasigeodesic is a closed curve on the surface of a polyhedron with at most $180^\circ$ of surface on both sides at all points; such curves can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm establishes for the first time a quasipolynomial upper bound on the total number of visits to faces (number of line segments), namely, $O\left(\frac{n \, L^3}{ε^2 \, \ell^3}\right)$ where $n$ is the number of vertices of the polyhedron, $ε$ is the minimum curvature of a vertex, $L$ is the length of the longest edge, and $\ell$ is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face). On the real RAM, the algorithm's running time is also pseudopolynomial, namely $O\left(\frac{n \, L^3}{ε^2 \, \ell^3} \log n\right)$. On a word RAM, the running time grows to $O\left(b^2 \cdot \frac{n^8 \log n}{ε^8} \cdot \frac{L^{21}}{\ell^{21}}\cdot 2^{O(|Λ|)}\right)$, where $|Λ|$ is the number of distinct edge lengths in the polyhedron, assuming its intrinsic or extrinsic geometry is given by rational coordinates each with at most $b$ bits. This time bound remains pseudopolynomial for polyhedra with $O(\log n)$ distinct edges lengths, but is exponential in the worst case. Along the way, we introduce the expression RAM model of computation, formalizing a connection between the real RAM and word RAM hinted at by past work on exact geometric computation.
