Lower Bounds for Streets and Generalized Streets
[.ps]
[.pdf]
Abstract
We present lower bounds for on-line searching problems in two special classes of simple polygons called streets and generalized streets. In streets we assume that the location of the target is known to the robot in advance and prove a lower bound of
√2 on the competitive ratio of any deterministic search strategy which can be shown to be tight. For generalized streets we show that if the location of the target is not known, then there is a class of orthogonal generalized streets for which the competitive ratio of any search strategy is at least
√82 ~ 9.06 in the
L2-metric---again matching the competitive ratio of the best known algorithm. We also show that if the location of the target is known, then the competitive ratio for searching in generalized streets in the
L1-metric is at least 9 which also can be shown to be tight. The former result is based on a lower bound on the average competitive ratio of searching on the real line if an upper bound of $D$ to the target is given. We show that in this case the average competitive ratio is at least
9 - O(1/log D).
Bibtex Entry
