  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}{\epsilon^2 \, \ell^3}\right)$
where $n$ is the number of vertices of the polyhedron, $\epsilon$ 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}{\epsilon^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}{\epsilon^8} \cdot
\frac{L^{21}}{\ell^{21}}\cdot 2^{O(|\Lambda|)}\right)$, where $|\Lambda|$ 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.
