Article ID: | iaor20001551 |
Country: | Netherlands |
Volume: | 93 |
Issue: | 1 |
Start Page Number: | 67 |
End Page Number: | 73 |
Publication Date: | Apr 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Hipke Christoph, Icking Christian, Klein Rolf, Langetepe Elmar |
Keywords: | programming: geometric |
It is well known that on a line, a target point in unknown position can be found by walking a path at most 9 times as long as the distance from the start to the target point, in the worst case. This competitive factor of 9 is optimal. We investigate the case where the target is known to be within a fixed distance,