Competitive searching for a line on a line arrangement

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

42 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.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsDer-Tsai Lee, Chung-Shou Liao, Wen-Lian Hsu
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)978-3-95977-094-1
Publication statusPublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
ISSN (Electronic)1868-8969


Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CityJiaoxi, Yilan


  • Competitive searching
  • Detour factor
  • Line arrangement
  • Search strategy

Cite this