When Can a Polygon Fold to a Polytope?

Abstract

We show that the decision question posed in the title can be answered with an algorithm of time and space complexity O(n 2 ), for a polygon of n vertices. We use a theorem of Aleksandrov that says that if the edges of the polygon can be matched in length so that the resulting complex is homeomorphic to a sphere, and such that the "complete angle" at each vertex is no more than 2, then the implied folding corresponds to a unique convex polytope. We check the Aleksandrov conditions via dynamic programming. The algorithm has been implemented and tested. 1 Introduction The polygon shown in Fig. 1a cannot fold edge-to-edge to a convex polytope despite being composed of six squares that one might think could fold to a cube. The familiar "cross" polygon in Fig. 1b can of course fold to a cube. The aim of this paper is to provide an algorithm that can decide whether a polygon can fold to a polytope. We take a polygon P to be a collection of vertices (v 0 ; v 1 ; :::; v n\\Gamma1 ) in...