0
$\begingroup$

Imagine you are on an (in)finite 2d-plane (and confined to walk on it). There's a straight line somewhere on the plane, but you don't know where it is and neither can you find it by looking from afar. You have to cross it! What's the best walking strategy to find the line in the least time possible?

Edited: As of @Brandon_J and @Adam answers which close the question for the infinite plane, please consider answering the best strategy for the finite plane case. (If it is not a good policy to edit the scope of the question this way, please edit it back.)

My attempt

  1. Choose a random direction and walk for a distance of $r$
  2. Walk now along the circle of radius $r$
  3. If after the full circle you haven't met the line, increase the distance from the starting point by another amount of $r$
  4. Walk along the circle of radius $2r$
  5. Repeat the procedure until you cross the line
Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ Is the straight line infinite in length? $\endgroup$
    – Adam
    Feb 12, 2019 at 15:35
  • $\begingroup$ @Adam Yes, it is! $\endgroup$
    – Carlos
    Feb 12, 2019 at 15:43
  • $\begingroup$ New concern. You clearly brought up an issue of starting position however you haven't included any information on this matter in the question. Can you clarify if it is random or from the centre etc. $\endgroup$
    – Adam
    Feb 12, 2019 at 16:42
  • $\begingroup$ @Adam We start on a random position, and the line is in a random position. You can even be "close" to the line, but you don't know where it is unless you walk past it. $\endgroup$
    – Carlos
    Feb 12, 2019 at 16:45
  • $\begingroup$ I edited the question to "least time possible" to avoid answers where one walks till the boundary of the plane (which might be really really far away) and then goes along the perimeter (as per @Adam solution). $\endgroup$
    – Carlos
    Feb 12, 2019 at 16:59

2 Answers 2

Reset to default
3
$\begingroup$

I would recommend walking in a

spiral shape, somewhat like so: Spiral

This way you won't miss the line, and you'll eventually cover the entire plane if

You're given infinite time. You're not, and in searching an infinite plane for a line the odds are infinitely against you.

While my solution is possibly better than your solution, both of your solutions will likely

NEVER WORK. Ever. It's an infinite plane. Walk a million miles and you haven't begun to cover one-millionth of the plane in your search. Walk a billion miles and you haven't covered a billionth of the plane. Walk a trillion miles and you haven't even covered a trillionth of the plane - you aren't ever making actual progress.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Indeed, infinite plane was definitely too much to ask for! There's no optimal solution, of course. I had thought about the spiral solution, but depending on how you choose the spiral parameters you might end up walking more distance to obtain the same information, isn't it? $\endgroup$
    – Carlos
    Feb 12, 2019 at 15:49
  • $\begingroup$ spoiler. If you follow an exponential spiral, the distance you will have to travel is proportional to the distance from your starting point to the line. If you follow a linear spiral, the distance you'd have to travel is proportional to the square of the distance to the line. $\endgroup$
    – user3294068
    Feb 13, 2019 at 20:04
2
$\begingroup$

For the finite plane

A great solution is

Walk along the perimeter of the plane

Why?

The line you are looking for is infinite in length however it must pass through a finite plane so it must cross the perimeter!

Improve this answer
$\endgroup$
11
  • $\begingroup$ This is certainly not an optimal solution, as the boundary of the plane might be very far away from your starting point. Can we do better? $\endgroup$
    – Carlos
    Feb 12, 2019 at 16:17
  • $\begingroup$ You litterally can't walk on the perimeter of the plan because it's infinite. $\endgroup$
    – Rémi Henry
    Feb 12, 2019 at 16:19
  • $\begingroup$ He added a finite plane problem. Also @Carlos I think that Adam's answer here (for the finite plane, not the infinite plane) is optimal, or at least is the only way to guarantee that you find the line. $\endgroup$
    – Brandon_J
    Feb 12, 2019 at 16:31
  • $\begingroup$ @Brandon_J It is indeed a way with probability 1 of finding the line; but maybe there's another way with probability as close to 1 to find the line with less travelled distance. Would random walk work? $\endgroup$
    – Carlos
    Feb 12, 2019 at 16:41
  • 1
    $\begingroup$ That's not going to cover very much ground at all...and it isn't guaranteed to find a solution. $\endgroup$
    – Brandon_J
    Feb 12, 2019 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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