Using a string to map the world
Hui Wang, Michael R. M. Jenkin, Patrick W. Dymond · 2010
Literature and folklore is rife with a range of oracles that have been used by explorers to explore unknown environments. But how effective are these various oracles? This paper considers the power of string and string-like oracles to map an unknown embedded topological environment. We demonstrate that for undirected graphs, even very short strings can be used to explore an unknown environment but that significant performance improvements can be found when longer strings are available.