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

22 Downloads (Pure)

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.

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
DOIs
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)
Volume123
ISSN (Electronic)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

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

Cite this

Bouts, Q., Castermans, T., van Goethem, A., van Kreveld, M., & Meulemans, W. (2018). Competitive searching for a line on a line arrangement. In D-T. Lee, C-S. Liao, & W-L. Hsu (Eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018 [49] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 123). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2018.49