Lower Bounds for Searching in Streets and Generalized Streets. A. López-Ortiz and S. Schuierer. To appear IJCGA, 1999. PostScript file.

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 asssume that the location of the target is known to the robot in advance and prove a lower bound of $\sqrt{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 $\sqrt{82} \sim 9.06$ in the $L_2$-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 $L_1$-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 avervage competitive ratio is at least $9 - O(1/\log D)$.