Title: Centroidal localization game,
Abstract: One important problem in a network is to locate an (invisible) moving entity
by using distance-detectors placed at strategical locations. For instance, the
metric dimension of a graph $G$ is the minimum number $k$ of detectors placed
in some vertices $\{v_1,\cdots,v_k\}$ such that the vector $(d_1,\cdots,d_k)$
of the distances $d(v_i,r)$ between the detectors and the entity's location $r$
allows to uniquely determine $r \in V(G)$. In a more realistic setting, instead
of getting the exact distance information, given devices placed in
$\{v_1,\cdots,v_k\}$, we get only relative distances between the entity's
location $r$ and the devices (for every $1\leq i,j\leq k$, it is provided
whether $d(v_i,r) >$, $<$, or $=$ to $d(v_j,r)$). The centroidal dimension of a
graph $G$ is the minimum number of devices required to locate the entity in
this setting.
We consider the natural generalization of the latter problem, where vertices
may be probed sequentially until the moving entity is located. At every turn, a
set $\{v_1,\cdots,v_k\}$ of vertices is probed and then the relative distances
between the vertices $v_i$ and the current location $r$ of the entity are
given. If not located, the moving entity may move along one edge. Let $\zeta^*
(G)$ be the minimum $k$ such that the entity is eventually located, whatever it
does, in the graph $G$.
We prove that $\zeta^* (T)\leq 2$ for every tree $T$ and give an upper bound
on $\zeta^*(G\square H)$ in cartesian product of graphs $G$ and $H$. Our main
result is that $\zeta^* (G)\leq 3$ for any outerplanar graph $G$. We then prove
that $\zeta^* (G)$ is bounded by the pathwidth of $G$ plus 1 and that the
optimization problem of determining $\zeta^* (G)$ is NP-hard in general graphs.
Finally, we show that approximating (up to any constant distance) the entity's
location in the Euclidean plane requires at most two vertices per turn.