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

[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:

• The exact coordinates of each unknown point $n_j$ for which $\text{dist}(m_i, n_j)

• A list of all indices $j$ for which $\text{dist}(m_i, n_j) 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.)

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.

• Put all $m$ as 2D points in a spatial index

• 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).

• Now, by getting all other estimated measurements for a particular $n$, you can try to approximate the correct $n$

• (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.

StackExchange Computer Science Q#61057, answer score: 3