Finding Closed Quasigeodesics on Convex Polyhedra
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909857986117632 |
|---|---|
| author | Demaine, Erik D. Hesterberg, Adam C. Ku, Jason S. |
| author_facet | Demaine, Erik D. Hesterberg, Adam C. Ku, Jason S. |
| contents | 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 also establishes a pseudopolynomial upper bound on the total number of visits to faces (number of line segments), namely, $O\left(\frac{n \, L^2}{ε^2 \, \ell^2}\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{L^2}{ε^2 \, \ell^2} \, n \lg n\right)$. On a word RAM, the running time grows to $O\left(\frac{b^2 \, Δ^{36} \, L^{146}}{ε^{98} \, \ell^{146}} \, n \lg n \cdot 2^{O(|R|)}\right)$, where $Δ\leq n$ is the polyhedron's maximum vertex degree, assuming the polyhedron's intrinsic geometry is given by constant-size radical expressions with $b$-bit integers and at most $|R|$ distinct square-roots. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_00589 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Finding Closed Quasigeodesics on Convex Polyhedra Demaine, Erik D. Hesterberg, Adam C. Ku, Jason S. Computational Geometry Metric Geometry 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 also establishes a pseudopolynomial upper bound on the total number of visits to faces (number of line segments), namely, $O\left(\frac{n \, L^2}{ε^2 \, \ell^2}\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{L^2}{ε^2 \, \ell^2} \, n \lg n\right)$. On a word RAM, the running time grows to $O\left(\frac{b^2 \, Δ^{36} \, L^{146}}{ε^{98} \, \ell^{146}} \, n \lg n \cdot 2^{O(|R|)}\right)$, where $Δ\leq n$ is the polyhedron's maximum vertex degree, assuming the polyhedron's intrinsic geometry is given by constant-size radical expressions with $b$-bit integers and at most $|R|$ distinct square-roots. 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. |
| title | Finding Closed Quasigeodesics on Convex Polyhedra |
| topic | Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2008.00589 |