Advice complexity of treasure hunt in geometric terrains
Authors :- Andrzej Pelc & Ram Narayan Yadav
Publication :- Information and Computation, February 2021, 104705
Treasure hunt is finding an inert target by a mobile agent. We consider treasure hunt in polygonal terrains with polygonal obstacles. The agent finds the treasure when there is a segment of length at most 1 between them, inside the terrain. The cost of treasure hunt is the length of the agent's trajectory. We investigate the amount of information (advice complexity) needed for treasure hunt at cost linear in the length of a shortest path in the terrain from the initial position of the agent to the treasure. A polygon is c-fat if the ratio of the radius of the smallest disc containing it to the radius of the largest disc contained in it is at most c. For regular terrains, defined as convex polygons with convex c-fat obstacles, for some constant , we establish the exact advice complexity of treasure hunt. We then show that advice complexity of treasure hunt for arbitrary terrains is exponentially larger than for regular terrains.