Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

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

share|improve this question
9  
+1 for the picture, +1 for the nice problem. But I can upvote only once. :) –  Tsuyoshi Ito May 2 '11 at 0:14
5  
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 May 2 '11 at 0:57
3  
“[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 May 2 '11 at 11:21
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. –  Joseph O'Rourke May 3 '11 at 11:10
5  
"Maybe that's why it's so highly rated," said someone completely apathetic about complexity theory. –  JɛffE Jun 7 '13 at 3:00
show 19 more comments

1 Answer 1

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 a vertex (just walk backwards and extend l to the vertex)
  • The 2D space of starting positions and angles can be partitioned by the next vertex. So starting at vertex a, x units from the bottom, with an angle of a, we end up in vertex V after crossing one vertex.
  • At that point we're at another vertex 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. :)

share|improve this answer
10  
"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. –  JɛffE Jan 10 '12 at 11:30
    
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 Jan 10 '12 at 11:45
10  
Alas, generic geodesics on generic polyhedra are not periodic. (In particular, generic polygons are not rational.) –  JɛffE Jan 10 '12 at 16:29
add comment

protected by Artem Kaznatcheev Mar 30 at 19:35

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.