6
$\begingroup$

Pirates have buried treasure on a very unusual perfectly circular desert island, with no trees or obstacles of any kind. The map takes me to the island but doesn't tell me where to find it on the island.

It only tells me that it's buried under a small x marked on the ground.

The tide is coming in fast so I have to find my treasure as soon as possible, or risk drowning.

The island is 1km across in any direction.

I can only spot the small mark from 10 meters away (pirates were often short sighted).

What's the most efficient way to search the island? Should I walk around in a spiral? Cut the island into segments and cross the center many times? What's the best search pattern?

Edit: I should probably mention that I can use the treasure chest as a boat and won't drown if I find it.

$\endgroup$
  • $\begingroup$ I think ideally you're looking at a spiral pattern from outwards to center, but that's mostly intuition, and to account for the rising tide, so the outer regions are done asap before they flood. You just need to start 10m from the shoreline, walk in spiral to the center, just ensuring you move make a 20m walk inwards when about to close the circle you were on. (so basically a series on nearly complete circles, then just step inwards for the next, in a spiral-like pattern). No proof though, so just commenting. $\endgroup$ – Tim Couwelier Oct 14 '14 at 9:51
  • $\begingroup$ Concentric circles would be quicker than a spiral I believe, since the spiral requires a full circumference before you can start spiralling inwards, whereas concentric circles only require one radius of overhead (where you step in 10m after each circle) $\endgroup$ – Joe Oct 14 '14 at 10:07
  • 1
    $\begingroup$ But with perfect circles you loose time after you completed one circle to move to the next circle. It would be better to have a transition phase where you move diagonally to the next circle. $\endgroup$ – Florian F Oct 14 '14 at 10:32
  • $\begingroup$ This is basically Paint the rectangle with least movement except with a circular target area. $\endgroup$ – Moyli Oct 14 '14 at 11:01
  • $\begingroup$ Yep this is paint with a 20 meter brush. $\endgroup$ – corsiKa Oct 14 '14 at 15:17
6
$\begingroup$

I believe the concentric circles would be the best way to cover the ground. Depending on the size of the "x" a spiral would cause you to miss a portion of the island unless you started the spiral off the island. Starting 10 meters in at a radius 490 meters you would make a circle and step in 20 meters and repeat until you are 10 meters from the center where your last circle would cover the rest.

for (int R = 490; R >= 10; R-=20)
    total+=(2*Pi*R) + 20)

return total-10

subtracting 10 because we only had to walk in 10 meters for the first circle results in

39759.91 meters with 25 concentric circles.
$\endgroup$
  • 1
    $\begingroup$ It's very hard to do much better than this: The island's area is about $0.785 km^2$ and the shortest route to cover that area with a 10 meter line of sight (walking a straight line) is about 39254 meters. $\endgroup$ – Moyli Oct 14 '14 at 14:15
  • $\begingroup$ 40km! That's quite a long walk (5 hours at a trot), but this is probably the best. it also keeps ahead of the tide maybe. $\endgroup$ – d'alar'cop Oct 14 '14 at 14:15
  • $\begingroup$ You could try to first walk around the island once and then start spiraling towards the center, but I don't know if that would make it shorter. $\endgroup$ – Moyli Oct 14 '14 at 14:16
  • $\begingroup$ I suspect this may essentially be a very angular spiral anyway, you've factored in a 20m walk between each circle. But as far as I can tell this is the correct approach. $\endgroup$ – AJFaraday Oct 14 '14 at 14:45
  • $\begingroup$ You could optimize this slightly. For your path, the last 10m of each circle is redundant. Everything you see you have either already seen, or will see as you turn to move to the next circle. Turning early would cut off 10m from each circle, for a saving of about 250m. $\endgroup$ – user3294068 Feb 13 at 20:33

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.