2024/01/02 by Sarita de Berg, de Berg, Sarita, Nathan van Beusekom +7 · 2 citations
Computer Science · Engineering · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Guidance and Control Systems #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2401.01289
openalex publication_date 2024/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a variant of the searching problem where the environment consists of a known terrain and the goal is to obtain visibility of an unknown target point on the surface of the terrain. The searcher starts on the surface of the terrain and is allowed to fly above the terrain. The goal is to devise a searching strategy that minimizes the competitive ratio, that is, the worst-case ratio between the distance traveled by the searching strategy and the minimum travel distance needed to detect the target. For 1.5D terrains we show that any searching strategy has a competitive ratio of at least √(82) and we present a nearly-optimal searching strategy that achieves a competitive ratio of 3√(19/2) ≈ √(82) + 0.19. This strategy extends directly to the case where the searcher has no knowledge of the terrain beforehand. For 2.5D terrains we show that the optimal competitive ratio depends on the maximum slope λ of the terrain, and is hence unbounded in general. Specifically, we provide a lower bound on the competitive ratio of Ω(√λ). Finally, we complement the lower bound with a searching strategy based on the maximum slope of the known terrain, which achieves a competitive ratio of O(√λ).