Advice complexity of treasure hunt in geometric terrains

DOI10.1016/J.IC.2021.104705MaRDI QIDQ2051769zbMATH OpenOpenAlexFDO

Authors Andrzej Pelc, R. N. Yadav

Publication date 25 November 2021

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.06823

zbMATH Keywords

mobile robotobstaclepolygontreasure hunt

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Treasure hunt with advice
• Deterministic treasure hunt in the plane with angular hints
• Treasure hunt in graph using pebbles
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• scientific article; zbMATH DE number 1154599

Cites work

• Approximate distance oracles
• Communication algorithms with advice
• Compact labeling schemes for ancestor queries. (Extended abstract)
• Deterministic Graph Exploration with Advice
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Distance labeling in graphs
• Exploring sparse graphs with advice (extended abstract)
• Exploring unknown environments with obstacles
• Graph searching with advice
• How to learn an unknown environment. I
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 871902 (Why is no real title available?)
• scientific article; zbMATH DE number 6297684 (Why is no real title available?)
• Labeling Schemes for Flow and Connectivity
• Local MST computation with short advice
• Navigating in Unfamiliar Geometric Terrain
• On the two-dimensional cow search problem
• Online computation with advice
• Online graph exploration with advice
• Online Navigation in a Room
• Proof labeling schemes
• Reaching a target in the plane with no information
• Searching for an axis-parallel shoreline
• Searching in the plane
• Shortest paths without a map
• The polygon exploration problem
• The theory of search games and rendezvous.
• Trade-offs between the size of advice and broadcasting time in trees
• Treasure hunt with advice
• Watchman routes under limited visibility
• Worst-case optimal exploration of terrains with obstacles

Cited in

(9)

• Pebble guided near optimal treasure hunt in anonymous graphs
• Deterministic treasure hunt in the plane with angular hints
• Treasure hunt with advice
• An explanatory, transformation geometry proof of a classic treasure-hunt problem and its generalization
• scientific article; zbMATH DE number 7561402 (Why is no real title available?)
• Impact of knowledge on the cost of treasure hunt in trees
• Treasure hunt in graph using pebbles
• Online search with a hint
• Deterministic treasure hunt and rendezvous in arbitrary connected graphs

This page was built for publication: Advice complexity of treasure hunt in geometric terrains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051769)