4
$\begingroup$

I read a story about somebody getting lost in a forest, and, apart from sympathy, the following mathematical problem came to my mind.

Suppose the lost person is sitting still at an unknown point in a square SxS forest (I saw a couple of questions on here where the person is assumed to be moving, but that seems harder).

A ranger starts search at the edge of the square, and they can spot the lost person within distance R.

What is the shortest-length path that the ranger can take to guarantee that they'll find the lost person? i.e. What is the shortest-length curve, whose extension by R covers the whole square. I wonder if it approaches one of the space filling curves (e.g. Peano) or is there a better way?

$\endgroup$
  • 1
    $\begingroup$ You may want to take a look at section of 7.6 of Planning Algorithms. $\endgroup$ – Rodrigo de Azevedo Feb 3 '17 at 23:32
  • $\begingroup$ The methodical Descartes has a straightforward solution for the lost person (rangers were scarce in his day): keep walking in a straight line. From a ranger's point of view, the question is more interesting. $\endgroup$ – Edward Porcella Feb 5 '17 at 16:57
0
$\begingroup$

Thank you @jkff for an interesting question. Without claiming to provide full answer, it seems that the optimal path (shortest walk for the ranger) is the one that does not cover any area twice. There is probably many of those. One straightforward example is drawn below. The length of the path is $\lfloor\frac{S}{R}\rfloor(S+R)+S$. Each component (highlighted by alternating red and blue) has length $S+R$ and there is $\lfloor\frac{S}{R}\rfloor$ of those. The last component covers the remaining part of the forest.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, this is a reasonable requirement (do not cover any area twice), but I'm not sure that this particular path is optimal in that sense. More precisely: we would like to maximize the additional area covered by each additional elementary segment of the curve; the long straight lines are clearly optimal in that sense - but the vertical lines, might be not so much. $\endgroup$ – jkff Feb 3 '17 at 18:59
  • $\begingroup$ @jkff I agree that the vertical elements have sense of sub-optimality. Let me also observe that, despite the fact that I used that term myself, it is not really clear one would define 'do not over any area twice', since when the ranger moves, he is constantly doing that. $\endgroup$ – Jan Feb 3 '17 at 19:01

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.