Paper by Erik D. Demaine
- Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams, “Rolling Polyhedra on Tessellations”, in Proceedings of the 11th International Conference on Fun with Algorithms (FUN 2022), Island of Favignana, Sicily, Italy, May 30–June 3, 2022, 5:1–5:16.
We study the space reachable by rolling a 3D convex polyhedron on a 2D
periodic tessellation in the xy-plane, where at every step a face of
the polyhedron must coincide exactly with a tile of the tessellation it rests
upon, and the polyhedron rotates around one of the incident edges of that face
until the neighboring face hits the xy plane. If the whole plane can
be reached by a sequence of such rolls, we call the polyhedron a plane
roller for the given tessellation. We further classify polyhedra that
reach a constant fraction of the plane, an infinite area but vanishing
fraction of the plane, or a bounded area as hollow-plane rollers,
band rollers, and bounded rollers respectively. We present a
polynomial-time algorithm to determine the set of tiles in a given periodic
tessellation reachable by a given polyhedron from a given starting position,
which in particular determines the roller type of the polyhedron and
tessellation. Using this algorithm, we compute the reachability for every
regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform
- The paper is available in PDF (2971k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated May 4, 2022 by