Algorithm for solving planar constraint problem ("Pokemon Go monster finding")

Question

[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 there are $N$ points (the "unknown points") in a plane, call them $n_1,\dots,n_N$, with unknown coordinates. Moreover, we have $M$ measurements taken at known locations $m_1,\dots,m_M$.

Let $\text{dist}(m_i, n_j)$ be the (generally unknown) Euclidean distance from measurement point $m_i$ to the unknown point $n_j$.

For each measurement $m_i$, we have the following information:

1. The exact coordinates of each unknown point $n_j$ for which $\text{dist}(m_i, n_j)<d_\text{min}$ for some known constant $d_\text{min}$; and
2. A list of all indices $j$ for which $\text{dist}(m_i, n_j) < d_\text{max}$ for some known constant $d_\text{max}>d_\text{min}$, sorted by $\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_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.)

Answer 1

I think you could use a "spatial join". I haven't played the game, but I assume $d_{max}$ is rather small, i.e. there are in the order of 10 or so $n$ and $m$ in the neighborhood of each $m$. I further assume that $N$ and $M$ are large, say 1,000,000 or more.

1. Put all $m$ as 2D points in a spatial index
2. For each $m_1$ in the index, perform a spatial range query with distance $2*d_{max}$. This gives you all other $m_x$ that can potentially contain the same $n$ as $m_1$. This should be manageable because the number of $m_x$ should be small (as I assumed above).
3. Now, by getting all other estimated measurements for a particular $n$, you can try to approximate the correct $n$
4. (Potential optimisation): Depending on your spatial index, you can remove the $m_1$ after processing all it's $n$. This makes the dataset smaller for the following range queries. Also,

Somehow you would also need to uniquely identify each $n$, so that you don't calculate the position of $n$ again if it turns up when processing another $m$.

As an optimisation, you may want to use window queries (rectangular) rather than circular range queries. Window queries can be much faster and give only slightly more results. Also, it could be that the game actually does not use euclidean distance (circles) but the faster manhatten distance, which would be exactly a rectangle.

For such a spatial join you can use any spatial index, such as R-Tree, kd-Tree, quadtree or any of their variants.

For large datasets I would probably not use a R-Tree (R+tree, R*-tree, X-Tree), or a special variant of the quadtree, the PH-Tree, which is well suited for range queries as well as allowing fast removal (or addition) of points.

For Java, implementations of R-Trees can be found in the anywhere on the internet, for example in the ELKI framework or my own TinSpin Index library. The PH-Tree is also available in Java.

A generic spatial join algorithm is called TOUCH, but I don't think it is open source.

Answer 2

If some object position $n_j$ is known exactly (e.g., because it is within $d_{min}$ of some measurement), then whenever this $n_j$ appears in the annulus for some measurement $m_i$ (meaning $d_{min} \le dist(m_i, n_j) < d_{max}$), we can shrink the possible regions for other unknown positions in that same annulus. Specifically, we can simply calculate $d_{ij} = dist(m_i, n_j)$ since we know both positions ($m_i$ and $n_j$) exactly, and we can then split the annulus for $m_i$ into two sub-annuli: a "near" piece (containing all points $p$ such that $d_{min} \le dist(m_i, p) < d_{ij}$) and a "far" piece (containing all points $p$ such that $d_{ij} \le dist(m_i, p) < d_{max}$). Every object listed before $n_j$ for measurement $m_i$ is necessarily confined to the near annulus, and every object listed after $n_j$ is confined to the far annulus.

What can be done (beyond the intersection of annuli already suggested by Tom van der Zanden in a comment) for object positions that aren't related to some already-known object position in this way? This seems very hard. The statement

"$n_j$ cannot appear at $p$"

is equivalent to

"For all possible placements of all remaining unknown points, setting $n_j = p$, together with the distance inequalities implied by the order in which objects belonging to the annulus of each measurement are listed, leads to a contradiction".

It seems to me that to get anywhere, we need to have (at least) 2 unknown object positions that appear in the annulus of (at least) the same 2 measurements. But while this information will rule out many pairs of positions for the two objects, I wasn't able to come up with any circumstance in which a position could be ruled out for just one of them, independently of the other object's position.