Finding weakly simple closed quasigeodesics on polyhedral spheres

DOI10.1007/S00454-023-00511-2MaRDI QIDQ6145671zbMATH OpenOpenAlexFDO

Authors Jean Chartier, Arnaud de Mesmay

Publication date 9 January 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.05853

zbMATH Keywords

quasigeodesicsdisk flowcurve-shortening processpolyhedral spheres

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Geodesics in global differential geometry (53C22)

Abstract: 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 $pi$ 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.

Recommendations

• Finding weakly simple closed quasigeodesics on polyhedral spheres
• Finding closed quasigeodesics on convex polyhedra
• Convex polyhedra without simple closed geodesics
• On the length of simple closed quasigeodesics on convex surfaces
• A necessary and sufficient condition for the existence of simple closed geodesics on regular tetrahedra in spherical space

Cites work

• scientific article; zbMATH DE number 3864035 (Why is no real title available?)
• scientific article; zbMATH DE number 3612083 (Why is no real title available?)
• scientific article; zbMATH DE number 1128877 (Why is no real title available?)
• scientific article; zbMATH DE number 857402 (Why is no real title available?)
• scientific article; zbMATH DE number 3061866 (Why is no real title available?)
• scientific article; zbMATH DE number 3063640 (Why is no real title available?)
• A Pseudopolynomial Algorithm for Alexandrov’s Theorem
• A course in metric geometry
• Alexandrov's theorem, weighted Delaunay triangulations, and mixed volumes
• Constructing monotone homotopies and sweepouts
• Convex Polyhedra
• Detecting weakly simple polygons
• Discrete and computational geometry
• Finding closed quasigeodesics on convex polyhedra
• Geometric folding algorithms. Linkages, origami, polyhedra
• Lectures on Polytopes
• Recognizing weakly simple polygons
• Riemannian geometry.
• Shellable Decompositions of Cells and Spheres.
• Shortening curves on surfaces
• Shortening embedded curves
• Tracing compressed curves in triangulated surfaces

Cited in

(2)

• Finding closed quasigeodesics on convex polyhedra
• Finding weakly simple closed quasigeodesics on polyhedral spheres

This page was built for publication: Finding weakly simple closed quasigeodesics on polyhedral spheres

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145671)