2026-08-16T14:53:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:868 2024-03-06T11:07:06Z ddc:004 open_access

Competitive Online Searching for a Ray in the Plane Eubeler, Andrea Fleischer, Rudolf Kamphans, Tom Klein, Rolf Langetepe, Elmar Trippen, Gerhard Online motion planning competitive analysis ray search We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal. First, we give a search strategy for a special case of the ray search---the window shopper problem---, where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrea Eubeler and Rudolf Fleischer and Tom Kamphans and Rolf Klein and Elmar Langetepe and Gerhard Trippen 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06421.5 urn:nbn:de:0030-drops-8687 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.5 eng https://creativecommons.org/licenses/by/4.0/legalcode