<p>This problem is very very difficult.  We could simplify it to make it easier, as follows.</p>

<ol>
<li><p>We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of $\pi$.  This gets rid of most "polytopes" but there are still many interesting possibilities: for example, the platonic solids. </p></li>
<li><p>We can assume that the polytope is not truly three-dimensional, but instead is the "double" of a polygon; this looks a bit like a pillowcase. We can simplify even further and suppose that the polygon has equal and parallel sides; for example a square, as in the game Astroids.</p></li>
</ol>

<p>If we make both of these assumptions then there is a large theory.  (Finding an $O(\log(\ell))$ algorithm for the square is a difficult exercise involving the continued fraction expansion of the angle of Mario's path.  To achieve a similar result for the regular octagon is possible but harder.  The solutions for the square and the octagon involve thinking about how to efficiently encode a "cutting sequences for a geodesic on a translation surface".  Most other rational polygons will quickly lead to open problems.)  An initial reference, which includes a further reference to Caroline Series's discussion of the square torus, are <a href="http://www.math.northwestern.edu/~diana/math/tufts.pdf" rel="noreferrer">these talk slides</a> by Diana Davis.</p>

<p>If we do not assume rationality, but do assume that the polytope is the double of a polygon, then we are discussing the theory of "cutting sequences in irrational billiards".  It seems that essentially nothing is known here; for example see the final sentence of <a href="http://people.maths.ox.ac.uk/tanner/Prospects2010/CUlcigraiTalk.pdf" rel="noreferrer">this talk</a> by Corinna Ulcigrai.</p>

<p>If we make neither assumption, well, I can't think of anything in the literature. </p>

<p>Finally - I'll guess that there is an $O(\log(\ell))$ solution to the Super Mario Galaxy problem for the platonic solids.  This is a good problem for a graduate student getting started in rational billiards.  For example, the case of the dodecahedron "should" follow from Diana Davis's thesis.  (But start with the tetrahedron - that will follow from an analysis of cutting sequences for the hexagonal torus.)</p>

CC BY-SA 3.0
2016-10-29T21:19:10.960Z
2016-11-01T08:09:43.510Z
2016-11-01T08:09:43.510Z
Sam Nead
<p>I think you can do better than linear. I'm new to theoretical computer science, so forgive me if this is rubbish.</p>

<p>Some general ideas (of varying value):</p>

<ul>
<li>If we give each facet a symbol, Mario's orbit over them can be described as a string, where the final symbol in the string is the answer.</li>
<li>We can assume without loss of generality that Mario starts on an edge (just walk backwards and extend l to the edge)</li>
<li>The 2D space of starting positions and angles can be partitioned by the next edge. So starting at edge a, x units from the bottom, with an angle of a, we end up in edge V after crossing one facet.</li>
<li>At that point we're at another edge with another orientation, so we can call the function recursively to subdivide the space into partitions of 2-symbol strings and so on.</li>
<li>At this point we're finished if we say that the space has to be discretized for the problem to be implemented on a TM. That means that every orbit must be periodic because there are only finitely many points on the discretized planet. We can calculate the function described above until we have orbits for all starting points and store this information. Then the problem becomes O(1).</li>
<li>Maybe that's a bit of a cop out. Some googling tells me that almost all billiard orbits inside rational convex polygons are periodic (ie. the periodic orbits are dense). So for a (say) square planets the same approach might work.</li>
<li>Another approach would be to consider the system as a generator/recognizer of strings (again by assigning each facet its own symbol). If the language has a known complexity class, that's your answer. If you broaden the family of polytopes to non-convex and any dimension, you may capture a very broad class of languages. </li>
</ul>

<p>This doesn't really constitute an answer, but I need to get back to work. :)</p>

CC BY-SA 3.0
2012-01-10T11:30:07.140Z
"At this point we're finished if we say that the space has to be discretized for the problem to be implemented on a TM. That means that every orbit must be periodic because there are only finitely many points on the discretized planet."  You've just destroyed the interesting part of the problem.  I do *not* want to assume the input is discrete; I want to solve the actual continuous problem, even though this requires an ideal computer that can do exact real arithmetic in constant time.  In particular, Mario's path need not ever touch a vertex.
Jeffε
CC BY-SA 3.0
2012-01-10T11:45:57.020Z
I figured that was too easy. You could do the continuous version on a finite machine, so long as the starting point and planet can be finitely described. You can just represent the path symbolically (mathematica-style). You only need to evaluate certain bounds to find which facet you end up in.  


If you can prove that the path is almost certainly periodic (as it is for billiards on rational convex polygons), you can still apply the same trick, but the result wouldn't be very practical.
Peter
CC BY-SA 3.0
2012-01-10T16:29:11.353Z
Alas, generic geodesics on generic polyhedra are not periodic.  (In particular, generic polygons are not rational.)
Jeffε
CC BY-SA 3.0
2015-10-18T10:03:24.787Z
You (Peter) are, I think, referring to the paper "Periodic billiard orbits are dense in rational polygons".  This does _not_ mean that periodic paths are _generic_ in rational polygons.  In fact, there are only countable many periodic paths (up to parallelism) so they have no chance of being generic.
Sam Nead
CC BY-SA 3.0
2015-10-18T10:04:15.730Z
In fact, in a "Veech" polygon the "uniquely ergodic" paths are full measure.  So if we send Mario is an random direction, he will (a) never hit a vertex (as Jeffe says in the problem statement), (b) his path will never close up, and (c) at large scales, the sequence of visited faces will look random (due to a "weak mixing" property).  This doesn't suggest a negative answer to the problem -- for example, the digits of pi also look random...
Sam Nead
CC BY-SA 3.0
2012-01-10T10:04:22.053Z
2016-08-02T15:20:41.433Z
2016-08-02T15:20:41.433Z
Peter
<p>Suppose Mario is walking on the surface of a planet.  If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?</p>

<p><a href="https://i.sstatic.net/hvaiP.jpg" rel="noreferrer"><img src="https://i.sstatic.net/hvaiP.jpg" alt="enter image description here"></a></p>

<p>More formally, suppose we are given a convex polytope $P$ in 3-space, a starting point $s$ on the surface of $P$, a direction vector $v$ (in the plane of some facet containing $p$), and a distance $\ell$.  How quickly can we determine which facet of $P$ Mario will stop inside?  (As a technical point, assume that if Mario walks into a vertex of $P$, he immediately explodes; fortunately, this <a href="http://en.wikipedia.org/wiki/Almost_never" rel="noreferrer">almost never</a> happens.)</p>

<p>Or if you prefer: suppose we are given the polytope $P$, the source point $s$, and the direction vector $v$ in advance.  After preprocessing, how quickly can we answer the question for a given distance $\ell$?</p>

<p>It's easy to simply trace Mario's footsteps, especially if $P$ has only triangular facets.  Whenever Mario enters a facet through one of its edges, we can determine in $O(1)$ time which of the other two edges he must leave through.  Although the running time of this algorithm is only linear in the number of edge-crossings, it's <em>unbounded</em> as a function of the input size, because the distance $\ell$ could be arbitrarily larger than the diameter of $P$.  Can we do better? </p>

<p>(In practice, the path length isn't actually unbounded; there is a global upper bound in terms of the number of bits needed to represent the input.  But insisting on integer inputs raises some rather nasty numerical issues — How do we compute <em>exactly</em> where to stop? — so let's stick to real inputs and exact real arithmetic.)</p>

<p>Is anything nontrivial known about the complexity of this problem?</p>

<p><strong>Update:</strong> In light of julkiewicz's comment, it seems clear that a real-RAM running time bounded purely in terms of $n$ (the complexity of the polytope) is impossible.  Consider the special case of a two-sided unit square $[0,1]^2$, with Mario starting at $(0,1/2)$ and walking in direction $(1,0)$.  Mario will stop on the front or the back of the square depending on the parity of the integer $\lfloor \ell \rfloor$.  We can't compute the floor function in constant time on the real RAM, unless we're happy <a href="http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html" rel="noreferrer">equating PSPACE and P</a>.  But we can compute $\lfloor \ell \rfloor$ in $O(\log \ell)$ time by exponential search, which is an exponential improvement over the naive algorithm.  <strong>Is time polynomial in $n$ and $\log \ell$ always achievable?</strong></p>

CC BY-SA 3.0
2011-05-02T00:26:59.823Z
A variation: Decide whether Mario will explode while he is traveling for the distance l.  This may be as hard as your problem (and if it is, it is a nice decision problem), but I do not know.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-02T00:57:15.127Z
I thought of a simpler problem, that is: we have a plain polygon and a beam of light traveling from a given point. When it reaches an edge it just gets mirrored. We want to know where the beam will end its travel after the given distance. It could (almost) be reduced to this one, by taking a polytope that is a prism of a very small height with the top and bottom sides in a shape of a given polygone. Maybe solving this first could help.
julkiewicz
CC BY-SA 3.0
2011-05-02T02:27:45.133Z
@Julkiewicz: A two-sided planar polygon is a degenerate convex polytope; it's the limit of a prism of height ε as ε goes to zero.  So yes, your problem is a special case of Mario's.
Jeffε
CC BY-SA 3.0
2011-05-02T11:21:37.953Z
“[T]ime polynomial in n and log l” does not make sense to me.  If it depends on l, it must also depend on the coordinates of P, and if you add log of all the numbers in the input, that is exactly the number of bits needed to represent the input when the input coordinates are restricted to integers.  I think that you are looking at the time complexity on a real RAM when the input is given as a bit string.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-03T11:10:42.173Z
Even deciding if Mario *ever* hits a vertex (independent of $\ell$) seems difficult.  I think here we run into the many unknowns in the area of billiard dynamics.
Joseph O'Rourke
CC BY-SA 3.0
2011-05-03T15:07:43.217Z
A simpler description: given a string of length $l$, fixed to a point on the surface of the polyhedron, where will the other string be when it is stretched on the surface along a particular direction?
Rob
CC BY-SA 3.0
2011-05-03T22:08:20.667Z
@Tsuyoshi: Yes, you're right.  So perhaps the right goal is polynomial in $n$ and $\log \Delta$, where $\Delta$ is the ratio of $\ell$ and the length of the shortest edge in $P$.  Or something.
Jeffε
CC BY-SA 3.0
2011-05-13T11:50:46.863Z
For each edge it's possible to create a sorted set of sorted sets of polygons, in which Mario will travel depending on the direction he is on current edge. It's a binary search to find a set based on the edge position, a binary search to find a polygon sequence in a set based on current direction, and it's a binary search to find the polygon, at which Mario stops, if current polygon set can exhaust the path, or the edge at which the next step should be taken. The complexity of this algorithm is based on the 3 binary searches and all they depend on maximum length of precomped polygon sequences.
George Polevoy
CC BY-SA 3.0
2011-09-07T04:59:26.707Z
Wouldn't it be more logical to determine the radius of the galaxy first? The haversine formula is an equation important in navigation, giving great-circle distances between two points on a sphere from their longitudes and latitudes. It is a special case of a more general formula in spherical trigonometry, the law of haversines, relating the sides and angles of spherical "triangles".
gotnull
CC BY-SA 3.0
2011-09-07T14:10:30.593Z
But the triangles in my proposed problem are flat, not spherical.
Jeffε
CC BY-SA 3.0
2012-03-16T13:59:13.190Z
Not really related, but this paper about the NP-Completeness of Super Mario is really amazing: http://arxiv.org/pdf/1203.1895v1.pdf
Lamine
CC BY-SA 3.0
2012-06-09T00:44:36.823Z
What does “equating #PSPACE and P” mean?  That looks like a type error to me.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-09T03:14:46.350Z
@TsuyoshiIto: Follow the link.  In a RAM model of computation that supports arithmetic operations on _arbitrary_ integers in constant time, one can solve any problem in #PSPACE in polynomial time.
Jeffε
CC BY-SA 3.0
2012-06-09T03:40:34.933Z
Did you follow the link?
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-09T11:50:57.400Z
Thanks for fixing the link.  Sorry for asking without reading the cited papers, but I cannot follow the logic stated in the page.  If QBF can be solved in polynomial-time using the model, isn’t it obvious that #SAT can be also solved, because QBF is PSPACE-complete and each bit of the answer of #SAT is in PP and hence in PSPACE?  Also, I do not think that the link talks about #PSPACE.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-09T12:56:28.470Z
The techniques used to solve #SAT and QBF in polynomial "time" can be combined fairly easily to solve #QBF in polynomial "time". (I didn't realize this until after I posted the linked text.)
Jeffε
CC BY-SA 3.0
2012-06-09T18:59:01.940Z
I do not know how to define #QBF.  Is it more difficult than QBF?  If you define #PSPACE as the class of counting problems associated with polynomially-balanced, PSPACE-decidable relations, then I think that it is equivalent to FPSPACE, the function version of PSPACE, unlike the case of #P.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-09T19:01:34.527Z
Also, my original concern still remains: P is a class of decision problems.  If #PSPACE is a class of functions, they are never equal because they have different types.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-09T19:45:04.387Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/3725/discussion-between-je-and-tsuyoshi-ito)
Jeffε
CC BY-SA 3.0
2012-06-10T07:04:40.337Z
In your update, a reference to $\ell$ is missing - how does it show up in the unit square problem ?
Suresh Venkat
CC BY-SA 3.0
2012-11-12T09:59:42.983Z
The problem seems to be easy if one can cut the polytope along some edges, unfold it into plane, and then this unfolded figure tiles the plane (i.e. covers the whole plane without overlap), like in your two sided square example. Otherwise, one needs branching, e.g. to attach another plane polygon which may depend on the direction. It may be possible to use symmetries, but if symmetries are broken, e.g. all facets has different symmetry, it is not clear at all how to use them.
mkatkov
CC BY-SA 3.0
2013-06-06T15:26:54.557Z
long wondering/curious, can anyone explain why this question is so highly rated? it has interesting aspects but just doesnt seem to be connected to any major complexity theory problems or famous open conjectures etc...
vzn
CC BY-SA 3.0
2013-06-07T03:00:05.717Z
"Maybe that's why it's so highly rated," said someone completely apathetic about complexity theory.
Jeffε
CC BY-SA 3.0
2014-07-29T20:39:31.570Z
@mkatkov I was also thinking that unfolding may improve the problem, but then I found this : G.C. Shephard, Convex Polytopes with Convex Nets. Math. Proc. Camb. Phil. Soc., 78:389-403 (1975), and apparently the question "Can every convex polyhedron be cut along its edges and unfolded flat to a single, non-overlapping, simple polygon," i.e., a single connected flat component is still open!
daaxix
CC BY-SA 3.0
2014-08-13T16:11:47.577Z
idea for bridge theory: there is some deep math research into a field known as "rational billiards" which looks at the trajectory of a billiard ball on polygonal tables which seems similar, & also looks at periodic tilings of the polygonal table surfaces. suspect there may be some connections to the Super Mario Galaxy problem... ran across some of this reading about new Fields medalist winner [Mirzakhani](http://www.simonsfoundation.org/quanta/20140812-a-tenacious-explorer-of-abstract-surfaces/)...
vzn
CC BY-SA 3.0
2016-05-31T22:45:03.290Z
this paper was just found by [EJS](http://cs.stackexchange.com/users/35842/eviljs) & seems closest published research to the problem so far. [THE DISCRETE GEODESIC PROBLEM](https://www.cs.umd.edu/~mount/Papers/mmp-sicomp-87.pdf) / Mitchell, Mount, Papadimitriou
vzn
CC BY-SA 3.0
2016-07-25T12:33:04.903Z
I'm new to this site from stack exchange and I very much like this problem. I would leave an answer on how I would treat or tackle this problem but my reputation isn't high enough yet.
Francis Cugler
CC BY-SA 3.0
2017-01-25T19:06:56.993Z
This is not an algorithm... For any face the trajectory is coming from some edge and is going to another edge. In at most the N edge crossings one of the faces will be visited twice (N is the number of faces).  One can color all trajectories leading from this face to itself. Then repeat for uncolored region. There would be long precomputing, but you will end up with edge maps showing distances for each colored regions. Than I guess one can use exponentiation algorithm for same face travel.
mkatkov
CC BY-SA 3.0
2016-08-04T04:55:23.583Z
do you have planet speed at time ?
mussdroid
CC BY-SA 4.0
2022-09-09T08:56:15.013Z
I am pretty much a layman, but why is this so hard? I'm thinking one could A) "unwrap" the planet, make the surface repeat somehow and just walk a straight line on the surface B) We can do calculations with lines on curved surfaces like a sphere, no? Or calculations with lines on a surface of, say, cube? Why is it that we apparently can't construct a line starting from some point on a sphere or a cube, make it certain length while wrapping around the object and figure out where the end point of that line is?
Swiffy
CC BY-SA 4.0
2022-09-09T23:31:17.817Z
@Swiffy The question is not whether it can be done at all; the brute-force tracing procedure you described works just fine.  The question is whether it can be done faster than that.  Do we really _need_ to separately consider each time Mario crosses over an edge of the polyhedron?  Note that if we somehow know in advance that Mario doesn't cross his own path, we _can_ beat the brute force algorithm!
Jeffε
<ds.algorithms><cg.comp-geom>
Super Mario Galaxy problem
Jeffε
# Super Mario Galaxy problem

(Asked by: username_0 on 2011-05-02)

Suppose Mario is walking on the surface of a planet. If he starts walking from a known location, in a fixed direction, for a predetermined distance, how quickly can we determine where he will stop?

[![enter image description here](https://i.sstatic.net/hvaiP.jpg)](https://i.sstatic.net/hvaiP.jpg)

More formally, suppose we are given a convex polytope $P$ in 3-space, a starting point $s$ on the surface of $P$, a direction vector $v$ (in the plane of some facet containing $p$), and a distance $\ell$. How quickly can we determine which facet of $P$ Mario will stop inside? (As a technical point, assume that if Mario walks into a vertex of $P$, he immediately explodes; fortunately, this [almost never](http://en.wikipedia.org/wiki/Almost_never) happens.)

Or if you prefer: suppose we are given the polytope $P$, the source point $s$, and the direction vector $v$ in advance. After preprocessing, how quickly can we answer the question for a given distance $\ell$?

It's easy to simply trace Mario's footsteps, especially if $P$ has only triangular facets. Whenever Mario enters a facet through one of its edges, we can determine in $O(1)$ time which of the other two edges he must leave through. Although the running time of this algorithm is only linear in the number of edge-crossings, it's *unbounded* as a function of the input size, because the distance $\ell$ could be arbitrarily larger than the diameter of $P$. Can we do better?

(In practice, the path length isn't actually unbounded; there is a global upper bound in terms of the number of bits needed to represent the input. But insisting on integer inputs raises some rather nasty numerical issues — How do we compute *exactly* where to stop? — so let's stick to real inputs and exact real arithmetic.)

Is anything nontrivial known about the complexity of this problem?

**Update:** In light of julkiewicz's comment, it seems clear that a real-RAM running time bounded purely in terms of $n$ (the complexity of the polytope) is impossible. Consider the special case of a two-sided unit square $[0,1]^2$, with Mario starting at $(0,1/2)$ and walking in direction $(1,0)$. Mario will stop on the front or the back of the square depending on the parity of the integer $\lfloor \ell \rfloor$. We can't compute the floor function in constant time on the real RAM, unless we're happy [equating PSPACE and P](http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html). But we can compute $\lfloor \ell \rfloor$ in $O(\log \ell)$ time by exponential search, which is an exponential improvement over the naive algorithm. **Is time polynomial in $n$ and $\log \ell$ always achievable?**

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: A variation: Decide whether Mario will explode while he is traveling for the distance l.  This may be as hard as your problem (and if it is, it is a nice decision problem), but I do not know.  
> **username_2**: I thought of a simpler problem, that is: we have a plain polygon and a beam of light traveling from a given point. When it reaches an edge it just gets mirrored. We want to know where the beam will end its travel after the given distance. It could (almost) be reduced to this one, by taking a polytope that is a prism of a very small height with the top and bottom sides in a shape of a given polygone. Maybe solving this first could help.  
> **username_0**: @Julkiewicz: A two-sided planar polygon is a degenerate convex polytope; it's the limit of a prism of height ε as ε goes to zero.  So yes, your problem is a special case of Mario's.  
> **username_1**: “[T]ime polynomial in n and log l” does not make sense to me.  If it depends on l, it must also depend on the coordinates of P, and if you add log of all the numbers in the input, that is exactly the number of bits needed to represent the input when the input coordinates are restricted to integers.  I think that you are looking at the time complexity on a real RAM when the input is given as a bit string.  
> **username_3**: Even deciding if Mario *ever* hits a vertex (independent of $\ell$) seems difficult.  I think here we run into the many unknowns in the area of billiard dynamics.  
> **username_4**: A simpler description: given a string of length $l$, fixed to a point on the surface of the polyhedron, where will the other string be when it is stretched on the surface along a particular direction?  
> **username_0**: @Tsuyoshi: Yes, you're right.  So perhaps the right goal is polynomial in $n$ and $\log \Delta$, where $\Delta$ is the ratio of $\ell$ and the length of the shortest edge in $P$.  Or something.  
> **username_5**: For each edge it's possible to create a sorted set of sorted sets of polygons, in which Mario will travel depending on the direction he is on current edge. It's a binary search to find a set based on the edge position, a binary search to find a polygon sequence in a set based on current direction, and it's a binary search to find the polygon, at which Mario stops, if current polygon set can exhaust the path, or the edge at which the next step should be taken. The complexity of this algorithm is based on the 3 binary searches and all they depend on maximum length of precomped polygon sequences.  
> **username_6**: Wouldn't it be more logical to determine the radius of the galaxy first? The haversine formula is an equation important in navigation, giving great-circle distances between two points on a sphere from their longitudes and latitudes. It is a special case of a more general formula in spherical trigonometry, the law of haversines, relating the sides and angles of spherical "triangles".  
> **username_0**: But the triangles in my proposed problem are flat, not spherical.  
> **username_7**: Not really related, but this paper about the NP-Completeness of Super Mario is really amazing: http://arxiv.org/pdf/1203.1895v1.pdf  
> **username_1**: What does “equating #PSPACE and P” mean?  That looks like a type error to me.  
> **username_0**: @TsuyoshiIto: Follow the link.  In a RAM model of computation that supports arithmetic operations on _arbitrary_ integers in constant time, one can solve any problem in #PSPACE in polynomial time.  
> **username_1**: Did you follow the link?  
> **username_1**: Thanks for fixing the link.  Sorry for asking without reading the cited papers, but I cannot follow the logic stated in the page.  If QBF can be solved in polynomial-time using the model, isn’t it obvious that #SAT can be also solved, because QBF is PSPACE-complete and each bit of the answer of #SAT is in PP and hence in PSPACE?  Also, I do not think that the link talks about #PSPACE.  
> **username_0**: The techniques used to solve #SAT and QBF in polynomial "time" can be combined fairly easily to solve #QBF in polynomial "time". (I didn't realize this until after I posted the linked text.)  
> **username_1**: I do not know how to define #QBF.  Is it more difficult than QBF?  If you define #PSPACE as the class of counting problems associated with polynomially-balanced, PSPACE-decidable relations, then I think that it is equivalent to FPSPACE, the function version of PSPACE, unlike the case of #P.  
> **username_1**: Also, my original concern still remains: P is a class of decision problems.  If #PSPACE is a class of functions, they are never equal because they have different types.  
> **username_0**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/3725/discussion-between-je-and-tsuyoshi-ito)  
> **username_8**: In your update, a reference to $\ell$ is missing - how does it show up in the unit square problem ?  
> **username_9**: The problem seems to be easy if one can cut the polytope along some edges, unfold it into plane, and then this unfolded figure tiles the plane (i.e. covers the whole plane without overlap), like in your two sided square example. Otherwise, one needs branching, e.g. to attach another plane polygon which may depend on the direction. It may be possible to use symmetries, but if symmetries are broken, e.g. all facets has different symmetry, it is not clear at all how to use them.  
> **username_10**: long wondering/curious, can anyone explain why this question is so highly rated? it has interesting aspects but just doesnt seem to be connected to any major complexity theory problems or famous open conjectures etc...  
> **username_0**: "Maybe that's why it's so highly rated," said someone completely apathetic about complexity theory.  
> **username_11**: @mkatkov I was also thinking that unfolding may improve the problem, but then I found this : G.C. Shephard, Convex Polytopes with Convex Nets. Math. Proc. Camb. Phil. Soc., 78:389-403 (1975), and apparently the question "Can every convex polyhedron be cut along its edges and unfolded flat to a single, non-overlapping, simple polygon," i.e., a single connected flat component is still open!  
> **username_10**: idea for bridge theory: there is some deep math research into a field known as "rational billiards" which looks at the trajectory of a billiard ball on polygonal tables which seems similar, & also looks at periodic tilings of the polygonal table surfaces. suspect there may be some connections to the Super Mario Galaxy problem... ran across some of this reading about new Fields medalist winner [Mirzakhani](http://www.simonsfoundation.org/quanta/20140812-a-tenacious-explorer-of-abstract-surfaces/)...  
> **username_10**: this paper was just found by [EJS](http://cs.stackexchange.com/users/35842/eviljs) & seems closest published research to the problem so far. [THE DISCRETE GEODESIC PROBLEM](https://www.cs.umd.edu/~mount/Papers/mmp-sicomp-87.pdf) / Mitchell, Mount, Papadimitriou  
> **username_12**: I'm new to this site from stack exchange and I very much like this problem. I would leave an answer on how I would treat or tackle this problem but my reputation isn't high enough yet.  
> **username_13**: do you have planet speed at time ?  
> **username_9**: This is not an algorithm... For any face the trajectory is coming from some edge and is going to another edge. In at most the N edge crossings one of the faces will be visited twice (N is the number of faces).  One can color all trajectories leading from this face to itself. Then repeat for uncolored region. There would be long precomputing, but you will end up with edge maps showing distances for each colored regions. Than I guess one can use exponentiation algorithm for same face travel.  
> **username_14**: I am pretty much a layman, but why is this so hard? I'm thinking one could A) "unwrap" the planet, make the surface repeat somehow and just walk a straight line on the surface B) We can do calculations with lines on curved surfaces like a sphere, no? Or calculations with lines on a surface of, say, cube? Why is it that we apparently can't construct a line starting from some point on a sphere or a cube, make it certain length while wrapping around the object and figure out where the end point of that line is?  
> **username_0**: @Swiffy The question is not whether it can be done at all; the brute-force tracing procedure you described works just fine.  The question is whether it can be done faster than that.  Do we really _need_ to separately consider each time Mario crosses over an edge of the polyhedron?  Note that if we somehow know in advance that Mario doesn't cross his own path, we _can_ beat the brute force algorithm!  

---

## 2 answers

### Answer by username_15 on 2016-10-29. Score: 9

This problem is very very difficult. We could simplify it to make it easier, as follows.

1. We can add the assumption that the angle sum about every vertex of the polytope $P$ is a rational multiple of $\pi$. This gets rid of most "polytopes" but there are still many interesting possibilities: for example, the platonic solids.
2. We can assume that the polytope is not truly three-dimensional, but instead is the "double" of a polygon; this looks a bit like a pillowcase. We can simplify even further and suppose that the polygon has equal and parallel sides; for example a square, as in the game Astroids.

If we make both of these assumptions then there is a large theory. (Finding an $O(\log(\ell))$ algorithm for the square is a difficult exercise involving the continued fraction expansion of the angle of Mario's path. To achieve a similar result for the regular octagon is possible but harder. The solutions for the square and the octagon involve thinking about how to efficiently encode a "cutting sequences for a geodesic on a translation surface". Most other rational polygons will quickly lead to open problems.) An initial reference, which includes a further reference to Caroline Series's discussion of the square torus, are [these talk slides](http://www.math.northwestern.edu/~diana/math/tufts.pdf) by Diana Davis.

If we do not assume rationality, but do assume that the polytope is the double of a polygon, then we are discussing the theory of "cutting sequences in irrational billiards". It seems that essentially nothing is known here; for example see the final sentence of [this talk](http://people.maths.ox.ac.uk/tanner/Prospects2010/CUlcigraiTalk.pdf) by Corinna Ulcigrai.

If we make neither assumption, well, I can't think of anything in the literature.

Finally - I'll guess that there is an $O(\log(\ell))$ solution to the Super Mario Galaxy problem for the platonic solids. This is a good problem for a graduate student getting started in rational billiards. For example, the case of the dodecahedron "should" follow from Diana Davis's thesis. (But start with the tetrahedron - that will follow from an analysis of cutting sequences for the hexagonal torus.)


---

### Answer by username_16 on 2012-01-10. Score: 0

I think you can do better than linear. I'm new to theoretical computer science, so forgive me if this is rubbish.

Some general ideas (of varying value):

* If we give each facet a symbol, Mario's orbit over them can be described as a string, where the final symbol in the string is the answer.
* We can assume without loss of generality that Mario starts on an edge (just walk backwards and extend l to the edge)
* The 2D space of starting positions and angles can be partitioned by the next edge. So starting at edge a, x units from the bottom, with an angle of a, we end up in edge V after crossing one facet.
* At that point we're at another edge with another orientation, so we can call the function recursively to subdivide the space into partitions of 2-symbol strings and so on.
* At this point we're finished if we say that the space has to be discretized for the problem to be implemented on a TM. That means that every orbit must be periodic because there are only finitely many points on the discretized planet. We can calculate the function described above until we have orbits for all starting points and store this information. Then the problem becomes O(1).
* Maybe that's a bit of a cop out. Some googling tells me that almost all billiard orbits inside rational convex polygons are periodic (ie. the periodic orbits are dense). So for a (say) square planets the same approach might work.
* Another approach would be to consider the system as a generator/recognizer of strings (again by assigning each facet its own symbol). If the language has a known complexity class, that's your answer. If you broaden the family of polytopes to non-convex and any dimension, you may capture a very broad class of languages.

This doesn't really constitute an answer, but I need to get back to work. :)

> **Comments:**
> **username_0**: "At this point we're finished if we say that the space has to be discretized for the problem to be implemented on a TM. That means that every orbit must be periodic because there are only finitely many points on the discretized planet."  You've just destroyed the interesting part of the problem.  I do *not* want to assume the input is discrete; I want to solve the actual continuous problem, even though this requires an ideal computer that can do exact real arithmetic in constant time.  In particular, Mario's path need not ever touch a vertex.  
> **username_16**: I figured that was too easy. You could do the continuous version on a finite machine, so long as the starting point and planet can be finitely described. You can just represent the path symbolically (mathematica-style). You only need to evaluate certain bounds to find which facet you end up in.     If you can prove that the path is almost certainly periodic (as it is for billiards on rational convex polygons), you can still apply the same trick, but the result wouldn't be very practical.  
> **username_0**: Alas, generic geodesics on generic polyhedra are not periodic.  (In particular, generic polygons are not rational.)  
> **username_15**: You (Peter) are, I think, referring to the paper "Periodic billiard orbits are dense in rational polygons".  This does _not_ mean that periodic paths are _generic_ in rational polygons.  In fact, there are only countable many periodic paths (up to parallelism) so they have no chance of being generic.  
> **username_15**: In fact, in a "Veech" polygon the "uniquely ergodic" paths are full measure.  So if we send Mario is an random direction, he will (a) never hit a vertex (as Jeffe says in the problem statement), (b) his path will never close up, and (c) at large scales, the sequence of visited faces will look random (due to a "weak mixing" property).  This doesn't suggest a negative answer to the problem -- for example, the digits of pi also look random...  

---

