Algorithm for solving planar constraint problem ("Pokemon Go monster finding")
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.