@inproceedings{de7a19672f3d403ea933e6f9edd59627,
title = "Competitive searching for a line on a line arrangement",
abstract = "We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Ω(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.",
keywords = "Competitive searching, Detour factor, Line arrangement, Search strategy",
author = "Quirijn Bouts and Thom Castermans and {van Goethem}, Arthur and {van Kreveld}, Marc and Wouter Meulemans",
year = "2018",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2018.49",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Der-Tsai Lee and Chung-Shou Liao and Wen-Lian Hsu",
booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",
note = "29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",
}