Position-Independent Near Optimal Searching and
On-line Recognition in Star Polygons. A. López-Ortiz and
S. Schuierer. Workshop on Algorithms and Data Structures. 1997.
PostScript file.
A previous version of this paper can be found in ACM Symp. on
Computational Geometry 1997.
Abstract.
We study the problem of on-line searching for a target inside a
polygon. In particular we propose a strategy for finding a target of
unknown location in a star polygon with a competitive ratio of 14.5,
and we further refine it to 12.72. This makes star polygons the first
non-trivial class of polygons known to admit constant competitive
searches independent of the position of the target. We also provide a
lower bound of 9 for the competitive ratio of searching in a star
polygon---which is close to the upper bound. A similar task consists
of the problem of on-line recognition of star polygons for which we
also present a strategy with a constant competitive ratio
including negative instances.