3
$\begingroup$

Inspired by Blindfolded and disoriented near the Great Wall of China

A drone is stationary at a spatial point about 1 m from the Great Wall, which is a vertical plane rectangle with height 5 m and infinite length. The altitude of the drone is a random number between 0 m and 5 m. The drone may be pointing in any direction (which may even be tilted upwards or downwards), however it does not know which. It can travel in any direction, and switch directions accurately. It gets to know when it touches the ground plane, and can then determine its own tilt upwards/downwards by travelling a small distance on the ground (about zero).

Q 1: What is the minimum distance that must be travelled to ensure it hits the Great Wall?

Q 2: If the objective is to minimise displacement between initial and final positions, what upper value can it be guaranteed to outperform?

|improve this question
$\endgroup$
  • $\begingroup$ A few points for clarification: (a) “about 1 m from the Great Wall”, and “a small distance on the ground (about 0)” — I guess we are to understand both these abouts to mean “to within some accuracy much smaller than all the other numbers involved”? (b) “a random integer between 0m and 5m” — by integer do you mean an integer number of metres, and (c) by random, do you mean “uniformly distributed random”? $\endgroup$ – Peter LeFanu Lumsdaine Jan 21 '16 at 16:11
  • $\begingroup$ What is the maximum angle at which this drone can be tilted? Could "forward" ever be straight up? $\endgroup$ – Ian MacDonald Jan 21 '16 at 16:58
  • $\begingroup$ @Peter (a) Yes, that is right. (b) Thanks for pointing out; I've edited the q. (c) Solution should work for every scenario and not based on probability $\endgroup$ – ghosts_in_the_code Jan 21 '16 at 17:28
  • 1
    $\begingroup$ I wish this problem did not have the height restriction, and instead had a drone searching for an infinite plane. That problem (which I've thought about for years but haven't made good progress on), has the allure of a potentially elegant solution. But your height restriction probably precludes an elegant solution, which makes it a less attractive puzzle in my opinion. $\endgroup$ – dshin Jan 21 '16 at 18:05
  • 1
    $\begingroup$ Making it an infinite wall also makes it fit into the generalization: How do you escape a $d$-dimensional forest if you know its size/shape and your distance from its boundary? $\endgroup$ – dshin Jan 21 '16 at 18:29
4
$\begingroup$

Q1: My initial approach would be to simply sculpt a sphere by going up sqrt(2) meters, then rotating around the initial point in a circle of radius sqrt(2). Three quarters of the way around, rotate 90* and start a second circle of radius sqrt(2) with the origin as center, perpendicular to the first. Three quarters of the way around that circle, rotate 90* again and create a third circle with the same origin / radius perpendicular to both the first two. When you finish that one, you'll be where you broke away from the second circle, so finish it off, then finish off the first circle. That gives you three perpendicular circles describing a sphere in distance sqrt(2)+6sqrt(2)pi = about 28 meters. Note that you need a radius of sqrt(2) to guarantee a hit with this method.

If you hit the ground at any point, continue along the surface on the projection of your original path onto the surface - this is necessarily less distance than the original path, so it can't hurt our distance in the worst case.

Q2: My approach never displaces further than sqrt(2) meters, but a method optimizing only displacement could simply travel the surface of the sphere of radius 1 centered at the origin in a chaotic path until it collided with the wall. The wall could be 1 meter away, so that is clearly optimal.

|improve this answer
$\endgroup$
  • $\begingroup$ You're right about q2 $\endgroup$ – ghosts_in_the_code Jan 22 '16 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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