Searching for an axis-parallel shoreline

Abstract: We consider the problem of searching for an unknown horizontal or vertical line in a plane. A search path in the plane starts at the origin and detects the unknown line, if the path hits the line for the first time. The performance of the search path is measured by competitive analysis. That is, we compute the ratio of the length of the path until the line is detected over the shortest path from the origin to the given line. The competitive ratio of a given search path is the worst-case ratio of the path among all horizontal and vertical lines in the plane. In this paper, we design a search path that attains a competitive ratio of , and slightly improves the current best-known search path. Furthermore, we prove that the search path is optimal among all paths that proceed in a cyclic manner. There is a strong conjecture that this path is the general optimal search path for searching axis-parallel lines. [Copyright &y& Elsevier]