English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Treasure hunt is the task of finding an inert target by a mobile agent in anunknown environment. We consider treasure hunt in geometric terrains withobstacles. Both the terrain and the obstacles are modeled as polygons and boththe agent and the treasure are modeled as points. The agent navigates in theterrain, avoiding obstacles, and finds the treasure when there is a segment oflength at most 1 between them, unobstructed by the boundary of the terrain orby the obstacles. The cost of finding the treasure is the length of thetrajectory of the agent. We investigate the amount of information that theagent needs a priori in order to find the treasure at cost $O(L)$, where $L$ isthe length of the shortest path in the terrain from the initial position of theagent to the treasure, avoiding obstacles. Following the paradigm of algorithmswith advice, this information is given to the agent in advance as a binarystring, by an oracle cooperating with the agent and knowing the wholeenvironment: the terrain, the position of the treasure and the initial positionof the agent. Advice complexity of treasure hunt is the minimum length of theadvice string (up to multiplicative constants) that enables the agent to findthe treasure at cost $O(L)$.  We first consider treasure hunt in regular terrains which are defined asconvex polygons with convex $c$-fat obstacles, for some constant $c>1$. Apolygon is $c$-fat if the ratio of the radius of the smallest disc containingit to the radius of the largest disc contained in it is at most $c$. For theclass of regular terrains, we establish the exact advice complexity of treasurehunt. We then show that advice complexity of treasure hunt for the class ofarbitrary terrains (even for non-convex polygons without obstacles, and evenfor those with only horizontal or vertical sides) is exponentially larger thanfor regular terrains.

Advice Complexity of Treasure Hunt in Geometric Terrains