Finding weakly simple closed quasigeodesics on polyhedral spheres

DOI10.1007/S00454-023-00511-2arXiv2203.05853OpenAlexW4382242669MaRDI QIDQ6145671FDOQ6145671

Authors: Jean Chartier, Arnaud de Mesmay 

Publication date: 9 January 2024

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

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.

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

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

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)

Cites Work

• A course in metric geometry
• Lectures on Polytopes
• Geometric folding algorithms. Linkages, origami, polyhedra
• Riemannian geometry.
• Shortening embedded curves
• Detecting weakly simple polygons
• Title not available (Why is that?)
• Shellable Decompositions of Cells and Spheres.
• Alexandrov's theorem, weighted Delaunay triangulations, and mixed volumes
• Convex Polyhedra
• Discrete and computational geometry
• Title not available (Why is that?)
• Shortening curves on surfaces
• Title not available (Why is that?)
• A Pseudopolynomial Algorithm for Alexandrov’s Theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognizing weakly simple polygons
• Title not available (Why is that?)
• Finding closed quasigeodesics on convex polyhedra
• Tracing compressed curves in triangulated surfaces
• Constructing monotone homotopies and sweepouts

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)