6 papers · 1 filter
Computing Homotopic Shortest Paths Efficiently
Alon Efrat, Stephen G. Kobourov, Anna Lubiw
This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm…
Enumerating Foldings and Unfoldings between Polygons and Polytopes
Erik D. Demaine, Martin L. Demaine, Anna Lubiw +1
We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous quest…
Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes
Erik D. Demaine, Martin L. Demaine, Anna Lubiw +1
We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope…
Locked and Unlocked Polygonal Chains in 3D
T. Biedl, E. Demaine, M. Demaine +8
In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a stra…
On Reconfiguring Tree Linkages: Trees can Lock
Therese Biedl, Erik Demaine, Martin Demaine +7
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfig…
Locked and Unlocked Polygonal Chains in 3D
T. Biedl, E. Demaine, M. Demaine +8
In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a stra…