2026-07-21T23:19:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9997 2024-03-06T10:45:18Z ddc:004 open_access

Competitive Searching for a Line on a Line Arrangement Bouts, Quirijn Castermans, Thom van Goethem, Arthur van Kreveld, Marc Meulemans, Wouter Competitive searching line arrangement detour factor search strategy 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 Omega(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Quirijn Bouts and Thom Castermans and Arthur van Goethem and Marc van Kreveld and Wouter Meulemans 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.49 urn:nbn:de:0030-drops-99970 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.49 eng https://creativecommons.org/licenses/by/3.0/legalcode