Continuous Flattening and Reversing of Convex Polyhedral Linkages

• DOI: 10.48550/arxiv.2412.15130
• Publication Date: 2024-01-01
• Authors: Demaine, Erik D.; Demaine, Martin L.; Hecher, Markus; Lin, Rebecca; Luo, Victor H.; Nara, Chie
• Keywords: Computational Geometry (cs.CG); FOS: Computer and information sciences; 68R10, 68Q17, 68U05; Discrete Mathematics (cs.DM); I.3.5; G.2.2; Computational Complexity (cs.CC); G.2.2; F.2.2; I.3.5; Computer Science - Computational Complexity; Computer Science - Data Structures and Algorithms; Computer Science - Computational Geometry; Data Structures and Algorithms (cs.DS); F.2.2; Computer Science - Discrete Mathematics

We prove two results about transforming any convex polyhedron, modeled as a linkage L of its edges. First, if we subdivide each edge of L in half, then L can be continuously flattened into a plane. Second, if L is equilateral and we again subdivide each edge in half, then L can be reversed, i.e., turned inside-out. A linear number of subdivisions is optimal up to constant factors, as we show (nonequilateral) examples that require a linear number of subdivisions. For nonequilateral linkages, we show that more subdivisions can be required: even a tetrahedron can require an arbitrary number of subdivisions to reverse. For nonequilateral tetrahedra, we provide an algorithm that matches this lower bound up to constant factors: logarithmic in the aspect ratio.