Approximately locating an invisible agent in a graph with relative distance queries

Abstract: In a pursuit evasion game on a finite, simple, undirected, and connected graph

G

, a first player visits vertices

m_{1}, m_{2}, l d o t s

of

G

, where

m_{i + 1}

is in the closed neighborhood of

m_{i}

for every

i

, and a second player probes arbitrary vertices

c_{1}, c_{2}, l d o t s

of

G

, and learns whether or not the distance between

c_{i + 1}

and

m_{i + 1}

is at most the distance between

c_{i}

and

m_{i}

. Up to what distance

d

can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that

d

is bounded by a constant. We conjecture that

d = O (l o g n)

for every graph

G

of order

n

, and show that

d = 0

if

m_{i + 1}

may differ from

m_{i}

only if

i

is a multiple of some sufficiently large integer.

Recommendations

Cites Work

This page was built for publication: Approximately locating an invisible agent in a graph with relative distance queries