# Finding a point in a 2D space

After sitting with this one for half a day, I'm not sure it is possible anymore, given my scenario.

The idea is to get a location on a map (coordinates) from some wifi data.

I have this wonderful system that on demand gives me my estimated position in a building. These positions are limited to a number of fixed points, meaning that if I am a few meters off, it will place me on the nearest fixed point. This system allows me to fetch the positions of all nearby fixed points in forms of coordinates (latitude, longitude), and wifi signal strength, which is how the position is estimated in the first place. That gives each of those fixed points two sets of data - Wifi strengths and coordinates. So for a given point, the data could be something like {A: -30dB, B: -67dB, C: -10dB}, {latitude 57.892305, longitude 54.234999}

The dB indicates the signal strength/distance from the wireless router. For now, I assume that this strength is linear (so that if the distance straight from A: -30dB and A: -40dB = 5 meters, then the distance between A: -30dB and 20dB = 5 meters).

All good so far.

Now what if I did not want an approximate fixed location, but an actual location, using these fixed points as reference? In other words, if I could get the signal strengths at any location, is there any way I could use the fixed points to calculate the coordinates of my current location?

I hope this is understandable, if not, please ask me to rephrase. :) I tried drawing the idea to make it clearer: http://i.imgur.com/i0RaBfy.png

-

## migrated from mathoverflow.netNov 12 '13 at 16:12

This question came from our site for professional mathematicians.

## 1 Answer

There is no really good answer to your question, because wifi signals are poor proxies for distance -- they are affected by walls, electronics, etc. That said, here is an optimization regime that will give you an answer.

Let the desired position be $(x,y)$, while the known locations are $(x_1,y_1),\ldots (x_n, y_n)$. Let the desired wifi strengths be $(a,b,c)$ while the known wifi strengths are $(a_1,b_1,c_1),\ldots, (a_n,b_n,c_n)$.

We first need a model for calculating wifi signal at a given spot knowing the data we know. Here is one way. Let $d_1'=d_1'(x,y)=\frac{1}{(x-x_1)^2+(y-y_1)^2}$, $d_2'=\frac{1}{(x-x_2)^2+(y-y_2)^2}, \ldots$, $d_n'=\frac{1}{(x-x_n)^2+(y-y_n)^2}$. We now normalize as $d_i=d_i(x,y)=\frac{d_i'}{d_1'+d_2'+\cdots+d_n'}$. The result is a set of positive real numbers $\{d_1,d_2,\ldots, d_n\}$ (depending on $x,y$), whose sum is $1$, and where larger numbers correspond to closer distance. With this, we define expected signal strengths $$a(x,y)=d_1a_1+d_2a_2+\cdots+d_na_n\\b(x,y)=d_1b_1+d_2b_2+\cdots+d_nb_n\\c(x,y)=d_1c_1+d_2c_2+\cdots+d_nc_n$$ This gives expected signal strength as a convex linear combination of the known signal strengths, with closer known nodes contributing a larger factor. Lastly, we want to incorporate our data to find $(x,y)$ as $$F(x,y)=(a-a(x,y))^2+(b-b(x,y))^2+(c-c(x,y))^2$$

This is an optimization problem in $x,y$ that can be solved numerically, or analytically with partial derivatives. The coordinates $(x,y)$ that minimize $F$ are the answer you seek.

-
Wauw. This was more elaborate than anything I could have hoped for. I need some time to run it through and understand it all properly, but your answer seems to spot on hit what I am trying to do :) Thank you! –  Treelink Nov 13 '13 at 8:33