Reconfigurations of polygonal structures
Greg Aloupis · 2005
This thesis contains new results on the subject of polygonal structure reconfiguration. Specifically, the types of structures considered here are polygons, polygonal chains, triangulations, and polyhedral surfaces. A sequence of vertices (points), successively joined by straight edges, is a polygonal chain. If the sequence is cyclic, then the object is a polygon. A planar triangulation is a set of vertices with a, maximal number of non-crossing straight edges joining them. A polyhedral surface is a three-dimensional structure consisting of flat polygonal faces that are joined by common edges. For each of these structures there exist several methods of reconfiguration. Any such method must provide a well-defined way of transforming one instance of a structure to any other. Several types of reconfigurations are reviewed in the introduction, which is followed by new results. We begin with efficient algorithms for comparing monotone chains. Next, we prove that flat chains with unit-length edges and angles within a wide range always admit reconfigurations, under the dihedral model of motion. In this model, angles and edge lengths are preserved. For the universal model, where only edge lengths are preserved, several types of hexagons that cannot be reconfigured are exhibited. New bounds are provided for the number of operations required to reconfigure between triangulations, using "point moves" and "edge flips". Finally, unfolding motions are proven to always be possible for specific slices of polyhedra.