<p>First of all, I think that you probably mean angular impulse and not torque. (You can look at impulse as the total effect of a torque applied over a short time.) If you neglect air drag etc., the motion of any rigid body (and in particular a coin or a cube) in the COM frame is very simple - it just rotates with a constant angular velocity. </p>

<p>This makes this problem kind of trivial. Just rotate the body by an angle $\omega t$ about the axis of rotation and find the side "facing up" by whatever geometric definition you want (it was not very clear in your description of the problem). If you are defining your top face as the face intersecting the vertical line passing through origin, things are even simpler. Rotate the line by angle $-\omega t$ about axis of rotation and find the intersecting face.</p>

<p>I would not say that this problem is a good model for the SMG problem because in SMG you have a point moving with constant speed on the surface whereas here the whole body will be rotating with a constant angular speed, which makes this problem so much simpler.</p>

CC BY-SA 3.0
2012-01-25T19:43:56.607Z
These are great observations. The goal was to make the problem similar in spirit, and "easier" than the SMG problem, without going so far as to make it trivial. Do you have any suggestions on how to redefine the problem to achieve these goals?
Joe
CC BY-SA 3.0
2012-01-26T21:28:32.347Z
I think that the Billiard problem (http://mathworld.wolfram.com/Billiards.html) on a closed 2D polygon and the related question "After a predetermined distance, to which side will the ball be closer?" can be a simplification of the SMG problem ... but I think it is still (very) hard!
Marzio De Biasi
CC BY-SA 3.0
2012-01-25T09:28:07.500Z
2012-01-25T09:28:07.500Z
Shitikanth
<p><b>
Edit: I think the spirit of the question was good, but it needs to be improved.
The assumptions made for the coin toss made that question trivial, and the die roll is still not precisely defined enough. </p>

<p>What are reasonable assumptions we can make about a die roll that make the question tractable, but non-trivial? The best place for any further discussion is probably in chat.</p>

<p></b></p>

<hr>

<p>This question is inspired by and closely related to the <a href="https://cstheory.stackexchange.com/questions/6356/super-mario-galaxy-problem">Super Mario Galaxy (SMG) problem</a>.</p>

<blockquote>
  <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>
</blockquote>

<p>As a first pass we would like to simplify the question as much as possible.</p>

<h3> Question 1 </h3> 

<p>Suppose we start with a coin heads face up, toss it with some initial torque $T$, and catch it again after time $t$. How quickly can we determine whether the coin will land on heads or tails?</p>

<p><img src="https://i.sstatic.net/0VYXp.gif" alt="Coin Toss animation"></p>

<p>To be more precise, a coin is a cylinder which has a height nearly 0 (negligible compared to its radius). 
The coin will rotate with constant angular velocity at a fixed angle for a fixed amount of time. At the end of that time period, we freeze time and space and examine the position of the coin. This is what is meant by "catching" the coin. There are three possibilities: the coin is exactly vertical, with the thin edge pointing precisely up. For now, we ignore this possibility. Thus, if you look at the coin from above, you can either see the heads side, or the tails side. Whichever side is visible from above at this instant is the value of the toss. </p>

<p>The initial torque and time period are meant to be analogous to Mario walking a fixed direction for a predetermined distance. The difference is that instead of walking along the surface of the polytope for some distance, we are letting it rotate freely in space for some fixed number of radians.</p>

<h3> Question 0 </h3>

<p>If the coin rotates around a fixed axis, is value of the toss (the side of the coin seen from above) periodic? As I defined the problem above, does the coin necessarily rotate around a fixed axis, or may it rotate more unpredictably?</p>

<p>As in the SMG problem, we would like to do something more clever than explicitly "walking" through each face as the coin flips. In this vastly simplified version of the problem, I believe this should be possible, because the coin flip should be periodic. </p>

<p>In the second question, we consider a less trivial restriction of the original problem.</p>

<h3> Question 2 </h3>

<p>Suppose that we roll an n-sided die from a given starting position $s$ with a given initial torque $T$, how quickly can we determine what will be the resulting value of the die roll?</p>

<p>We have to make some simplifying assumptions about the die, otherwise this becomes more of a physical modeling problem. For now, let's assume that we roll the die as we would toss a coin: we toss it, giving it some initial rotation, and after a short time catch it again, and whichever side lands face up is the value of the toss. </p>

<p>The unweighted version of the die roll problem is a restriction of the SMG problem in that the die must be a regular polytope, whereas the planet on which Mario walks may be any convex polytope $P$. Does the restriction to regular polytopes make the problem any easier?</p>

<h3> Question 3 </h3>

<p>Even for a regular die, I don't know that the sequence of faces which are face up will be periodic, but can we <em>approximate</em> the die roll by a periodic sequence and thus get a "best guess" of the result faster than we could solve the original problem? I think the answer is clearly yes, but what is the trade-off between the quality of our estimate and the improvement in running time?</p>

<h3> Question 4 </h3>

<p>Now suppose the die is weighted, so that it's velocity depends on the current face. In the terminology of the original <a href="https://cstheory.stackexchange.com/questions/6356/super-mario-galaxy-problem">SMG problem</a>, this means that the speed at which Mario walks depends on the face that Mario is currently in. Maybe some parts of the planet have rougher terrain than others.</p>

CC BY-SA 3.0
2012-01-23T22:47:42.900Z
@RickyDemer - The purpose of "catching" the coin is primarily to simplify the problem: that the coin or die does not continue to bounce and change it's rotation once it lands. The metaphor is that if you flip a coin and catch it in your palm, you cushion and cradle the coin a little, so that whatever side landed face up remains face up, as opposed to letting the coin land on the ground, where it may continue to rotate, or even reverse the direction of rotation.
Joe
CC BY-SA 3.0
2012-01-23T22:49:52.167Z
If "catching" the coin is a problematic metaphor, imagine instead that you toss it and take a picture of the coin while it's still in the air. Whichever side of the coin was facing the camera (the side you can see in the picture) is the value of the toss.
Joe
CC BY-SA 3.0
2012-01-24T07:50:22.967Z
What do you mean with "... initial Torque $T$"? Torque is a force. Do you mean that after the initial Torque the coin/die will rotate with constant angular velocity?
Marzio De Biasi
CC BY-SA 3.0
2012-01-24T10:19:19.393Z
I think you need to define your terms much more carefully before this question can be answered.  What *exactly* is a "coin"?  What is "initial torque"?  What does "catch" mean?  In short, what is the *precise* input to your problem?
Jeffε
CC BY-SA 3.0
2012-01-25T02:39:45.780Z
This is entirely tangential to your questions, but: "the die must be a regular polytope." I think the _must_ here is not clear. This is explored in the MathOverflow question, [Fair but irregular polyhedral dice](http://mathoverflow.net/questions/46684/).
Joseph O'Rourke
CC BY-SA 3.0
2012-01-26T20:32:24.287Z
The result of a die roll is predetermined the moment the die leaves your hand. Of course, you need knowledge impossible to obtain by a human to ascertain it. So, what exactly do you mean with "How quickly can **we** determine [the result]?"
Raphael
CC BY-SA 3.0
2012-01-26T21:09:51.667Z
@Joe the meta question you ask at the top of your question now is starting to turn this more into a discussion, then a focused question (it was already not that focused to start with the 4 subparts), which makes me want to cast a close-vote. I suggest considering [Suresh's proposal](http://meta.cstheory.stackexchange.com/q/1462/1037) and starting to ask the related questions in chat (make sure to @-tag some of the people who have been helpful so far, so they notice that discussion in chat and maybe help you more) to help developed a new more focused question like you desire.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-26T21:55:04.680Z
@Joe: Perhaps an easier die-like problem is: a 2D square box of size $n \times n$ rolls on an horizontal line, the line has a repeating finite pattern of dots $p_1,...,p_m$, with predetermined and varying distances $p_i - p_{i-1} > n$; the total length of the pattern is $w$. When the square box rolls over a dot placed at coordinates $k*w + p_i$ it "tilts" and its left-bottom corner is shifted right from position $x$ to position $(x + k*w+p_i) / 2$.
Marzio De Biasi
CC BY-SA 3.0
2012-01-26T21:55:51.640Z
@ArtemKaznatcheev I'm still learning the ropes on TCS stack exchange, so I don't know all the best-practices yet. Thanks for your suggestion to move to chat. Feel free to close-vote if you feel that the question should be closed at this point.
Joe
<ds.algorithms><cg.comp-geom>
Die roll problem
Joe
# Die roll problem

(Asked by: username_0 on 2012-01-23)

**Edit: I think the spirit of the question was good, but it needs to be improved.
The assumptions made for the coin toss made that question trivial, and the die roll is still not precisely defined enough.**

What are reasonable assumptions we can make about a die roll that make the question tractable, but non-trivial? The best place for any further discussion is probably in chat.

---

This question is inspired by and closely related to the [Super Mario Galaxy (SMG) problem](https://cstheory.stackexchange.com/questions/6356/super-mario-galaxy-problem).

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

As a first pass we would like to simplify the question as much as possible.

### Question 1

Suppose we start with a coin heads face up, toss it with some initial torque $T$, and catch it again after time $t$. How quickly can we determine whether the coin will land on heads or tails?

![Coin Toss animation](https://i.sstatic.net/0VYXp.gif)

To be more precise, a coin is a cylinder which has a height nearly 0 (negligible compared to its radius).
The coin will rotate with constant angular velocity at a fixed angle for a fixed amount of time. At the end of that time period, we freeze time and space and examine the position of the coin. This is what is meant by "catching" the coin. There are three possibilities: the coin is exactly vertical, with the thin edge pointing precisely up. For now, we ignore this possibility. Thus, if you look at the coin from above, you can either see the heads side, or the tails side. Whichever side is visible from above at this instant is the value of the toss.

The initial torque and time period are meant to be analogous to Mario walking a fixed direction for a predetermined distance. The difference is that instead of walking along the surface of the polytope for some distance, we are letting it rotate freely in space for some fixed number of radians.

### Question 0

If the coin rotates around a fixed axis, is value of the toss (the side of the coin seen from above) periodic? As I defined the problem above, does the coin necessarily rotate around a fixed axis, or may it rotate more unpredictably?

As in the SMG problem, we would like to do something more clever than explicitly "walking" through each face as the coin flips. In this vastly simplified version of the problem, I believe this should be possible, because the coin flip should be periodic.

In the second question, we consider a less trivial restriction of the original problem.

### Question 2

Suppose that we roll an n-sided die from a given starting position $s$ with a given initial torque $T$, how quickly can we determine what will be the resulting value of the die roll?

We have to make some simplifying assumptions about the die, otherwise this becomes more of a physical modeling problem. For now, let's assume that we roll the die as we would toss a coin: we toss it, giving it some initial rotation, and after a short time catch it again, and whichever side lands face up is the value of the toss.

The unweighted version of the die roll problem is a restriction of the SMG problem in that the die must be a regular polytope, whereas the planet on which Mario walks may be any convex polytope $P$. Does the restriction to regular polytopes make the problem any easier?

### Question 3

Even for a regular die, I don't know that the sequence of faces which are face up will be periodic, but can we *approximate* the die roll by a periodic sequence and thus get a "best guess" of the result faster than we could solve the original problem? I think the answer is clearly yes, but what is the trade-off between the quality of our estimate and the improvement in running time?

### Question 4

Now suppose the die is weighted, so that it's velocity depends on the current face. In the terminology of the original [SMG problem](https://cstheory.stackexchange.com/questions/6356/super-mario-galaxy-problem), this means that the speed at which Mario walks depends on the face that Mario is currently in. Maybe some parts of the planet have rougher terrain than others.

**Tags:** ds.algorithms, cg.comp-geom

> **Comments:**
> **username_0**: @RickyDemer - The purpose of "catching" the coin is primarily to simplify the problem: that the coin or die does not continue to bounce and change it's rotation once it lands. The metaphor is that if you flip a coin and catch it in your palm, you cushion and cradle the coin a little, so that whatever side landed face up remains face up, as opposed to letting the coin land on the ground, where it may continue to rotate, or even reverse the direction of rotation.  
> **username_0**: If "catching" the coin is a problematic metaphor, imagine instead that you toss it and take a picture of the coin while it's still in the air. Whichever side of the coin was facing the camera (the side you can see in the picture) is the value of the toss.  
> **username_1**: What do you mean with "... initial Torque $T$"? Torque is a force. Do you mean that after the initial Torque the coin/die will rotate with constant angular velocity?  
> **username_2**: I think you need to define your terms much more carefully before this question can be answered.  What *exactly* is a "coin"?  What is "initial torque"?  What does "catch" mean?  In short, what is the *precise* input to your problem?  
> **username_3**: This is entirely tangential to your questions, but: "the die must be a regular polytope." I think the _must_ here is not clear. This is explored in the MathOverflow question, [Fair but irregular polyhedral dice](http://mathoverflow.net/questions/46684/).  
> **username_4**: The result of a die roll is predetermined the moment the die leaves your hand. Of course, you need knowledge impossible to obtain by a human to ascertain it. So, what exactly do you mean with "How quickly can **we** determine [the result]?"  
> **username_5**: @username_0 the meta question you ask at the top of your question now is starting to turn this more into a discussion, then a focused question (it was already not that focused to start with the 4 subparts), which makes me want to cast a close-vote. I suggest considering [Suresh's proposal](http://meta.cstheory.stackexchange.com/q/1462/1037) and starting to ask the related questions in chat (make sure to @-tag some of the people who have been helpful so far, so they notice that discussion in chat and maybe help you more) to help developed a new more focused question like you desire.  
> **username_1**: @username_0: Perhaps an easier die-like problem is: a 2D square box of size $n \times n$ rolls on an horizontal line, the line has a repeating finite pattern of dots $p_1,...,p_m$, with predetermined and varying distances $p_i - p_{i-1} > n$; the total length of the pattern is $w$. When the square box rolls over a dot placed at coordinates $k*w + p_i$ it "tilts" and its left-bottom corner is shifted right from position $x$ to position $(x + k*w+p_i) / 2$.  
> **username_0**: @ArtemKaznatcheev I'm still learning the ropes on TCS stack exchange, so I don't know all the best-practices yet. Thanks for your suggestion to move to chat. Feel free to close-vote if you feel that the question should be closed at this point.  

---

## 1 answers

### Answer by username_6 on 2012-01-25. Score: 2 | Accepted answer

First of all, I think that you probably mean angular impulse and not torque. (You can look at impulse as the total effect of a torque applied over a short time.) If you neglect air drag etc., the motion of any rigid body (and in particular a coin or a cube) in the COM frame is very simple - it just rotates with a constant angular velocity.

This makes this problem kind of trivial. Just rotate the body by an angle $\omega t$ about the axis of rotation and find the side "facing up" by whatever geometric definition you want (it was not very clear in your description of the problem). If you are defining your top face as the face intersecting the vertical line passing through origin, things are even simpler. Rotate the line by angle $-\omega t$ about axis of rotation and find the intersecting face.

I would not say that this problem is a good model for the SMG problem because in SMG you have a point moving with constant speed on the surface whereas here the whole body will be rotating with a constant angular speed, which makes this problem so much simpler.

> **Comments:**
> **username_0**: These are great observations. The goal was to make the problem similar in spirit, and "easier" than the SMG problem, without going so far as to make it trivial. Do you have any suggestions on how to redefine the problem to achieve these goals?  
> **username_1**: I think that the Billiard problem (http://mathworld.wolfram.com/Billiards.html) on a closed 2D polygon and the related question "After a predetermined distance, to which side will the ball be closer?" can be a simplification of the SMG problem ... but I think it is still (very) hard!  

---

