Competitive searching for a line on a line arrangement

Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, Wouter Meulemans

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

25 Downloads (Pure)


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.

Originele taal-2Engels
Titel29th International Symposium on Algorithms and Computation, ISAAC 2018
RedacteurenDer-Tsai Lee, Chung-Shou Liao, Wen-Lian Hsu
Plaats van productieWadern
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's12
ISBN van elektronische versie978-3-95977-094-1
StatusGepubliceerd - 1 dec 2018
Evenement29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duur: 16 dec 201819 dec 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
ISSN van elektronische versie1868-8969


Congres29th International Symposium on Algorithms and Computation, ISAAC 2018
StadJiaoxi, Yilan

Citeer dit