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)$.