# Optimal curve to find a lost person in a forest

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?

• You may want to take a look at section of 7.6 of Planning Algorithms. – Rodrigo de Azevedo Feb 3 '17 at 23:32
• 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. – Edward Porcella Feb 5 '17 at 16:57

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. 