## An algorithmic approach to Rupert’s problem

HTML articles powered by AMS MathViewer

- by
Jakob Steininger and Sergey Yurkevich
**HTML**| PDF - Math. Comp.
**92**(2023), 1905-1929 Request permission

## Abstract:

A polyhedron $\mathbf {P} \subset \mathbb {R}^3$ has Rupert’s property if a hole can be cut into it, such that a copy of $\mathbf {P}$ can pass through this hole. There are several works investigating this property for some specific polyhedra: for example, it is known that all 5 Platonic and 9 out of the 13 Archimedean solids admit Rupert’s property. A commonly believed conjecture states that every convex polyhedron is Rupert. We prove that Rupert’s problem is algorithmically decidable for polyhedra with algebraic coordinates. We also design a probabilistic algorithm which can efficiently prove that a given polyhedron is Rupert. Using this algorithm we not only confirm this property for the known Platonic and Archimedean solids, but also prove it for one of the remaining Archimedean polyhedra and many others. Moreover, we significantly improve on almost all known Nieuwland numbers and finally conjecture, based on statistical evidence, that the Rhombicosidodecahedron is in fact*not*Rupert.

## References

- P. K. Agarwal, N. Amenta, and M. Sharir,
*Largest placement of one convex polygon inside another*, Discrete Comput. Geom.**19**(1998), no. 1, 95–104. MR**1486639**, DOI 10.1007/PL00009337 - András Bezdek, Zhenyue Guan, Mihály Hujter, and Antal Joós,
*Cubes and boxes have Rupert’s passages in every nontrivial direction*, Amer. Math. Monthly**128**(2021), no. 6, 534–542. MR**4265479**, DOI 10.1080/00029890.2021.1901461 - B. Chazelle,
*The polygon containment problem*, Adv. Comput. Res.**1**(1983), 1–33. - Ying Chai, Liping Yuan, and Tudor Zamfirescu,
*Rupert property of Archimedean solids*, Amer. Math. Monthly**125**(2018), no. 6, 497–504. MR**3806264**, DOI 10.1080/00029890.2018.1449505 - A. Fredriksson,
*The triakis tetrahedron and the pentagonal icositetrahedron are Rupert*, arXiv:2210.00601, 2022. - D. Yu. Grigor′ev and N. N. Vorobjov Jr.,
*Solving systems of polynomial inequalities in subexponential time*, J. Symbolic Comput.**5**(1988), no. 1-2, 37–64. MR**949112**, DOI 10.1016/S0747-7171(88)80005-1 - Balázs Hoffmann,
*Rupert properties of polyhedra and the generalised Nieuwland constant*, J. Geom. Graph.**23**(2019), no. 1, 29–35. MR**3982406** - Richard P. Jerrard, John E. Wetzel, and Liping Yuan,
*Platonic passages*, Math. Mag.**90**(2017), no. 2, 87–98. MR**3626279**, DOI 10.4169/math.mag.90.2.87 - Gérard Lavau,
*The truncated tetrahedron is Rupert*, Amer. Math. Monthly**126**(2019), no. 10, 929–932. MR**4033228**, DOI 10.1080/00029890.2019.1656958 - D. Schreck,
*Prince Rupert’s problem and its extension by Pieter Nieuwland*, Scripta Math.**16**(1950), 73–80, 261–267. - Christoph J. Scriba,
*Das Problem des Prinzen Ruprecht von der Pfalz*, Praxis Math.**10**(1968), no. 9, 241–246 (German). MR**497615** - M. I. Shamos,
*Computational Geometry*, PhD thesis, USA, 1978. AAI7819047. - J. Steininger and S. Yurkevich,
*Extended abstract for: solving Rupert’s problem algorithmically*, ACM Commun. Comput. Algebra**56**(2022), no. 2, 32–35. - P. Tonpho,
*Covering of objects related to Rupert property*, 2018. Master Thesis, http://cuir.car.chula.ac.th/handle/123456789/73138. - P. Tonpho and W. Wichiramala,
*Rupert property of some particular n-simplex and n-octahedrons*, June 2022. https://www.researchgate.net/publication/361602528_Rupert_property_of_some_particular_n-simplex_and_n-octahedrons.

## Additional Information

**Jakob Steininger**- Affiliation: Department of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Austria
- Email: steininger.jakob@yahoo.com
**Sergey Yurkevich**- Affiliation: Department of Mathematics, University of Vienna and Inria, Saclay, Oskar-Morgenstern-Platz 1, Room 02.124, Vienna, 1090, Austria
- MR Author ID: 1488630
- Email: sergey.yurkevich@univie.ac.at
- Received by editor(s): April 30, 2022
- Received by editor(s) in revised form: December 24, 2022
- Published electronically: February 28, 2023
- Additional Notes: The second author was financially supported by the DOC fellowship of the ÖAW (26101), the WTZ collaboration project of the OeAD (FR 09/2021) and the DeRerumNatura project ANR-19-CE40-0018.
- © Copyright 2023 American Mathematical Society
- Journal: Math. Comp.
**92**(2023), 1905-1929 - DOI: https://doi.org/10.1090/mcom/3831
- MathSciNet review: 4570346