Finding the wood by the trees
Marc J. van Kreveld · 1998
We'll give a strategy to locate all trees (points) from a starting tree using a rope, navigation equipment, computation, and some memory. 1 Introduction It is a well-known fact that it is sometimes difficult to see the wood for the trees. In this note it will be nontrivial to find even the trees which constitute a wood. Suppose an environment with a set of trees is given of which the locations are unknown. The number of trees is also unknown. Imagine that you are walking amidst the trees, but somehow all trees are invisible (for instance, suppose you are blind). However, you are equipped with perfect distance and heading sensors, a memory, exact computation for reals, a pair of legs, the possibility to walk along a straight line to a specified point, and a rope. Figure 1: Finding another tree. More abstractly, the trees are fixed points in the plane and the reader is a moving point. You are supposed to visit all trees (enumerate them), but you cannot see them. This is where the rope ...