next up previous
Next: Watchman Route Approaches Up: No Title Previous: Flushing out enemy forces

The One-Thief Case

Let's first consider the case of just one stationary thief. How can we locate the thief?

Of relevance here is the one-dimensional problem of locating a bridge on a river, if we don't know its location. There is a competitive algorithm for this problem, meaning that there is an algorithm which always finds a path whose distance is at most a constant factor of the length of the optimal path if we knew the the plan in advance. The competitive algorithm is based on a doubling argument. Travel one direction from the starting point for distance d. If you have not found the bridge, switch directions and travel for 2d in the other direction. Continue like this, doubling the distance each time, until you find the bridge. The ratio of the travel distance over the shortest-path to the bridge distance is constant because the travel length is a sum of terms of a geometric series.



Steve Skiena
Mon Oct 20 17:23:44 EDT 1997