4 ms·

You may have misread the problem. Consider a forest that is 1000km long but only 1km wide, it is possible that "walk straight ahead" has a worst case of 1000km

You may have misread the problem. Consider a forest that is 1000km long but only 1km wide, it is possible that "walk straight ahead" has a worst case of 1000km. But the strategy of "walk 1.5km, turn 90 degrees, walk 1.5km" has a worst case of 3km and is guaranteed to get you out of the forest (and I'm sure there are better strategies).

btilly 8y ago
The optimal strategy in this case is known and is called the Zallager curve. See http://www.wardsattic.com/joomla/Download/WebPresentation/zalgaller_escapes.htm http://www.wardsattic.com/joomla/Download/WebPresentation/za... for a picture.
- saagarjha 8y ago
  So you’re not too far off: the optimal value is 2.27.
  - deleted 8y ago
    [deleted]
- dunkelheit 8y ago
  Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.
- rocqua 8y ago
  What happens for a 1 : 1.1 rectangle? it seems to me that that curve isn't optimal then. If so, what is the ratio for a rectangle where that curve becomes optimal.
  - pwiecz 8y ago
    If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.
    - rocqua 8y ago
      thanks for the link!
    - gvb 8y ago
      That paper shows the value of visualization... I followed the Bellman Forest Problem link to the Wikipedia page on the Moser's Worm Problem[1] and it didn't do anything for me. In Ward's paper, he summarized Moser's Worm Problem differently (p.7): In 1966, Moser posed a related problem which roughly asks: “What's the best-shaped hammer for smashing one-inch worms?” Great visualization! [1] https://en.wikipedia.org/wiki/Moser%27s_worm_problem https://en.wikipedia.org/wiki/Moser%27s_worm_problem
FabHK 8y ago
In particular, the problem is to find a path that minimises the worst case (ie, which path minimises the time to hit the forest border over all possible starting locations and orientations within the forest).

btilly 8y ago

The optimal strategy in this case is known and is called the Zallager curve. See http://www.wardsattic.com/joomla/Download/WebPresentation/zalgaller_escapes.htm http://www.wardsattic.com/joomla/Download/WebPresentation/za... for a picture.

saagarjha 8y ago
So you’re not too far off: the optimal value is 2.27.
- deleted 8y ago
  [deleted]
dunkelheit 8y ago
Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.
rocqua 8y ago
What happens for a 1 : 1.1 rectangle? it seems to me that that curve isn't optimal then. If so, what is the ratio for a rectangle where that curve becomes optimal.
- pwiecz 8y ago
  If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.
  - rocqua 8y ago
    thanks for the link!
  - gvb 8y ago
    That paper shows the value of visualization... I followed the Bellman Forest Problem link to the Wikipedia page on the Moser's Worm Problem[1] and it didn't do anything for me. In Ward's paper, he summarized Moser's Worm Problem differently (p.7): In 1966, Moser posed a related problem which roughly asks: “What's the best-shaped hammer for smashing one-inch worms?” Great visualization! [1] https://en.wikipedia.org/wiki/Moser%27s_worm_problem https://en.wikipedia.org/wiki/Moser%27s_worm_problem

FabHK 8y ago

In particular, the problem is to find a path that minimises the worst case (ie, which path minimises the time to hit the forest border over all possible starting locations and orientations within the forest).