  Treasure hunt is the task of finding an inert target by a mobile agent in an
unknown environment. We consider treasure hunt in geometric terrains with
obstacles. Both the terrain and the obstacles are modeled as polygons and both
the agent and the treasure are modeled as points. The agent navigates in the
terrain, avoiding obstacles, and finds the treasure when there is a segment of
length at most 1 between them, unobstructed by the boundary of the terrain or
by the obstacles. The cost of finding the treasure is the length of the
trajectory of the agent. We investigate the amount of information that the
agent needs a priori in order to find the treasure at cost $O(L)$, where $L$ is
the length of the shortest path in the terrain from the initial position of the
agent to the treasure, avoiding obstacles. Following the paradigm of algorithms
with advice, this information is given to the agent in advance as a binary
string, by an oracle cooperating with the agent and knowing the whole
environment: the terrain, the position of the treasure and the initial position
of the agent. Advice complexity of treasure hunt is the minimum length of the
advice string (up to multiplicative constants) that enables the agent to find
the treasure at cost $O(L)$.
  We first consider treasure hunt in regular terrains which are defined as
convex polygons with convex $c$-fat obstacles, for some constant $c>1$. 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 the
class of regular terrains, we establish the exact advice complexity of treasure
hunt. We then show that advice complexity of treasure hunt for the class of
arbitrary terrains (even for non-convex polygons without obstacles, and even
for those with only horizontal or vertical sides) is exponentially larger than
for regular terrains.
