Hacker News Reader

Comment by gamegoblin | Hacker News Reader

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).

View on HN

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

So you’re not too far off: the optimal value is 2.27.

Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.

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.

If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.

thanks for the link!

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

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).

Reply on news.ycombinator.com