8
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ "sorted by $dist(m,n)$" - that is really nasty! Without this additional information you'd just have to take the intersection of a few annuli and be done with it, but the sorting gives you additional information that makes it hard. $\endgroup$ – Tom van der Zanden Jul 29 '16 at 6:45
  • $\begingroup$ It's not clear to me whether $N$ is known, nor what information is given for each $m$. Is the information given for $(X_1, Y_1)$ something like "Item 3 is at $(X_1+1,Y_1-0.2)$; the other nearby items are item 1, item 7, item 4 in that order"? $\endgroup$ – Peter Taylor Apr 12 '18 at 16:15
  • $\begingroup$ @PeterTaylor, Yes, that's right. See my edit. Is it clear now? $\endgroup$ – D.W. Apr 13 '18 at 3:52
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't see how this solves the problem. It lets you find all pairs $(m_i,n_j)$ for which unknown point $n_j$ is in range of measurement point $m_i$, but that doesn't seem like the hard part. The hard part is using that information to identify the set of possible locations for each $n_j$. What does the shape of that region look like? Can you output the exact region? How are you taking into account the information from order, as highlighted by Tom van der Zanden? $\endgroup$ – D.W. Apr 13 '18 at 3:55
  • $\begingroup$ Uh, blast from the past :-). "Spatial join" is something few people have heard of, so I thought it was the core of the question. I simply considered the answer for 'which region' to be 'around these point'. Apparently I misunderstood this. $\endgroup$ – TilmannZ Apr 13 '18 at 11:09
  • $\begingroup$ As far as I can tell, the resulting regions will be highly irregular, but easy enough to visualize by drawing a ring (between $d{min}$ and $d{max}$ around each $m$ (lest say with a faint green. If a ring overlaps with another ring, the green is intensified. After drawing all rings, remove all areas with non-maximal intensity of green. You can also do this completely in memory by 'drawing' the rings on a fine grained grid/matrix and simply increasing a counter in each grid cell. Is that what you are asking? $\endgroup$ – TilmannZ Apr 13 '18 at 11:17
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.