Document Open Access Logo

Rolling Polyhedra on Tessellations

Authors Akira Baes , Erik D. Demaine , Martin L. Demaine , Elizabeth Hartung , Stefan Langerman , Joseph O'Rourke , Ryuhei Uehara , Yushi Uno, Aaron Williams

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.6.pdf
  • Filesize: 3.03 MB
  • 16 pages

Document Identifiers

Author Details

Akira Baes
  • Département d'Informatique, Université libre de Bruxelles, Belgium
Erik D. Demaine
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Martin L. Demaine
  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA
Elizabeth Hartung
  • Department of Mathematics, Massachusetts College of Liberal Arts, North Adams, MA, USA
Stefan Langerman
  • Département d'Informatique, Université libre de Bruxelles, Belgium
Joseph O'Rourke
  • Department of Computer Science, Smith College, Northampton, MA, USA
Ryuhei Uehara
  • School of Information Science, Japan Advanced Institute of Science and Technology, Ishikawa, Japan
Yushi Uno
  • Graduate School of Informatics, Osaka Metropolitan University, Japan
Aaron Williams
  • Department of Computer Science, Williams College, Williamstown, MA, USA

Funding

  • Langerman, Stefan: Directeur de Recherches du F.R.S.-FNRS.
  • Uehara, Ryuhei: JSPS KAKENHI Grant Numbers JP18H04091, JP20H05961, JP20H05964, JP20K11673

Acknowledgements

Part of this work appeared in the first author’s Master’s Thesis. Part of this work was done at the 1st and 2nd Virtual Workshops on Computational Geometry (2020 and 2021). The authors would like to thank all participants of those workshops. Renders of prisms and antiprisms are by Robert Webb’s http://www.software3d.com/Stella.php. Other polyhedron renders are from Wikimedia Commons under Creative Commons Attribution license.

Cite AsGet BibTex

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 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.6

Abstract

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 tessellation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Discrete mathematics
Keywords
  • polyhedra
  • tilings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Jin Akiyama. Tile-makers and semi-tile-makers. The American Mathematical Monthly, 114(7):602-609, 2007. Google Scholar
  2. Jin Akiyama, Takayasu Kuwata, Stefan Langerman, Kenji Okawa, Ikuro Sato, and Geoffrey C. Shephard. Determination of all tessellation polyhedra with regular polygonal faces. In International Conference on Computational Geometry, Graphs and Applications, pages 1-11, 2010. Google Scholar
  3. Rachel Aouad Albashara, Luca Insisa, Quentin Magron, Dan Ngongo, Dang Phi L Pham, and Simon Yousfi. Rouler des polyèdres sur des tesselations. Université libre de Bruxelles Computer Science Bachelor Printemps des Sciences showcase, 2022. URL: https://akirabaes.com/polyrolly/printempsdessciences2022.
  4. Antonio Bicchi, Yacine Chitour, and Alessia Marigo. Reachability and steering of rolling polyhedra: a case study in discrete nonholonomy. IEEE Transactions on Automatic Control, 49(5):710-726, 2004. Google Scholar
  5. Kevin Buchin and Maike Buchin. Rolling block mazes are pspace-complete. Journal of Information Processing, 20(3):719-722, 2012. URL: https://doi.org/10.2197/ipsjjip.20.719.
  6. Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sándor Fekete, Christian Knauer, André Schulz, and Perouz Taslakian. On rolling cube puzzles. In Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Canada, August 2007. Google Scholar
  7. D. Chavey. Tilings by regular polygons - II: A catalog of tilings. Computers & Mathematics with Applications, 17(1-3):147-165, 1989. Google Scholar
  8. Yacine Chitour, Alessia Marigo, Domenico Prattichizzo, and Antonio Bicchi. Rolling polyhedra on a plane, analysis of the reachable set. In Algorithms for Robotic Motion and Manipulation (WAFR 1996), pages 277-285. 1997. Google Scholar
  9. Euclid. Elements, volume I. Circa 300 BCE. Google Scholar
  10. Judith V. Field. Rediscovering the archimedean polyhedra: Piero della francesca, luca pacioli, leonardo da vinci, albrecht dürer, daniele barbaro, and johannes kepler. Archive for History of Exact Sciences, 50(3/4):241-289, 1997. Google Scholar
  11. Martin Gardner. Martin Gardner’s Sixth Book of Mathematical Diversions from Scientific American. W H Freeman, San Francisco, 1971. Chapter 8. Google Scholar
  12. Martin Gardner. Mathematical Carnival. Borzoi / Alfred A Knopf, New York, 1975. Chapter 9, Problem 1: The red-faced cube. Google Scholar
  13. Martin Gardner. Time Travel and Other Mathematical Bewilderments. W H Freeman, New York, 1988. Chapter 9, Problem 8: Rolling cubes. Google Scholar
  14. B. Grünbaum and N. W. Johnson. The faces of a regular-faced polyhedron. Journal of the London Mathematical Society, 1(1):577-586, 1965. Google Scholar
  15. Branko Grünbaum and G. C. Shephard. Tilings and Patterns. W. H. Freeman and Company, 1987. Google Scholar
  16. Markus Holzer and Sebastian Jakobi. On the complexity of rolling block and Alice mazes. In Proceedings of the 6th International Conference on Fun with Algorithms, pages 210-222, 2012. Google Scholar
  17. Norman W Johnson. Convex polyhedra with regular faces. Canadian Journal of Mathematics, 18:169-200, 1966. Google Scholar
  18. Akihiro Uejima and Takahiro Okada. NP-completeness of rolling dice puzzles using octahedral and icosahedral dices (in Japanese). IEICE Trans. Fund., J94-A(8):621-628, 2011. Google Scholar
  19. Viktor Abramovich Zalgaller. Convex polyhedra with regular faces. Zapiski Nauchnykh Seminarov POMI, 2:5-221, 1967. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact