[Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to cheat, better information would be available more easily.]
Suppose we havethere are $N$ points (the "unknown points") in a plane, call them $n_1,\dots,n_N$, with unknown coordinates $(x_i, y_i)$, $1<i<N$. Moreover, we have $M$ measurements taken at known locations $(X_i, Y_i)$, $1<i<M$$m_1,\dots,m_M$.
Let $dist(m, n)$$\text{dist}(m_i, n_j)$ be the (generally unknown) Euclidean distance from measurement point $m$$m_i$ to the unknown point $n$$n_j$.
For each measurement $m$$m_i$, we have the following information:
- The exact coordinates of each unknown point $n$$n_j$ for which $dist(m, n)<d_{min}$$\text{dist}(m_i, n_j)<d_\text{min}$ for some known constant $d_{min}$$d_\text{min}$; and
- A list of all unknown pointsindices $n$$j$ for which $dist(m, n) < d_{max}$$\text{dist}(m_i, n_j) < d_\text{max}$ for some known constant $d_{max}>d_{min}$$d_\text{max}>d_\text{min}$, sorted by $dist(m, n)$$\text{dist}(m_i, n_j)$.
Is there an efficient algorithm for calculating the areas of the plane where the unknown points, or a given unknown point $n$$n_j$, can be? The algorithm is given the coordinates $(X_i,Y_i)$ of the measurement points, the measurement information listed above, and the number $N$ of unknown points; the goal is to narrow down the region of possible locations for each of the unknown points $n_1,\dots,n_N$ as much as possible.
The Pokemon connection:
In Pokemon Go, an augmented reality game, the goal is to find Pokemons in nature. Every now and then, the game shows the Pokemons in a "visible range" ($d_{min}$) of the player's position. Moreover, it has a "Pokemon finder" which shows a list of nearby ($dist<d_{max}$) Pokemons, sorted by distance. (It's also supposed to show an approximate distance as one, two or three footsteps, but apparently there's a bug and it always shows three footsteps.)
