My Location using google maps

We recently drove through Tulsa Oklahoma and stayed overnight at a Day's Inn and my laptop told me where we were:
How do they do that?
I can understand that my laptop can identify nearby WiFi hotspots (including the motel).
But locating a bunch of nearby hotspots ain't enough for google to locate my laptop.
It'd need distances from the hotspots as well.
At another motel with just two hotspots, google put us in the wrong state!

google maps

Okay, here's the problem:
  1. Your laptop PC provides the signal strength of nearby WiFi hotspots: 1 bar, 2 bars, 3 bars, etc.
    We'll call these strengths S1, S2, S3, etc.
  2. We assume that distance from your laptop to a hotspot is a known function of the signal strength: D = f(S).
    Then the distances to hotspots 1, 2, 3 etc. are: D1 = f(S1), D2 = f(S2) etc.
  3. The locations of the several hotspots are known: (x1, y1), (x2, y2) etc.
  4. Knowing the hotspot locations and the distances of your PC to each hotspot, determine the location of your PC.

>You're kidding, right? You see 3 bars on your PC and you can determine the distance to a hotspot?
This is science fiction ... so pay attention.
See Figure 1? There are three hotpsots and knowing three distances we can generate three circles.
The location we're looking for ("where's my PC?") is somewhere in (or near) that wee red circle.

For example there's a green circle and a blue circle with radii D1 and D2.
There are just two points which are a distance D1 from the green circle and a distance D2 from the blue circle.

>That's where the two circles intersect, right?
Right.


Figure 1: triangulation
Now we look at the points of intersection of the green and black and the blue and black.
Somewhere in the neighbourhood of all those intersections we'd expect to find your PC.
That's where we've stuck the little red circle.

>But why don't all three circles intersect at a single point?
They would ... in a perfect world. Alas, the signal strengths and are influenced by buildings, weather, PC orientation etc.
and that magic formula giving distance as a "known" function f of signal strength is a wild (educated?) guess.

Nevertheless, if we can locate your laptop (cell phone?) within a few metres (yards?), that'd be good, eh?
So let's get us a formula for the points of intersection of two circles.

>Then what?
Then, with our laptop, we'll take signal strength readings from known hotspots, assume some convenient function f and find out where we are.

>Wake me when you're finished ... zzzZZZ


Figure 2: a perfect world
For the hotspot locations, identified by (xj, yj), I can use latitude and longitude, right?
Okay, consider a couple of HotSpots at (x1, y1) and (x2, y2).
we determine that the distances to each are D1 and D2.
Then we expect our location is one of them red locations.
The location (x, y) of these two red points satisfy:
[1a]     (x - x1)2 + (y - y1)2 = D12   or   (x2 - 2 x x1 + x12) + (y2 - 2 y y1 + y12) = D12
[1b]     (x - x2)2 + (y - y2)2 = D22   or   (x2 - 2 x x2 + x22) + (y2 - 2 y y2 + y22) = D22

Figure 3: the Math
Now subtract 1a from 1b, fiddle a bit and get:
[2]     (x2 - x1)(x2 + x1 - 2 x) + (y2 - y1)(y2 + y1 - 2 y) = D22 - D12.

This is the equation of a straight line which passes through the two red points.
Now stand back and realize that each pair of circles provides such a straight line and ...

>And our laptop lies at the intersection of these lines, right?
Right ... in a perfect world, as illustrated in Figure 4a.

With three circles, we'll get three lines and they'll all intersect at a single point
... but that point might NOT be at the intersection of circles.
That's shown in Figure 4b where the intersection doesn't even lie on a circle.

>The lines will all intersect at a single point? Is that true?
Yes. We can see that in Figures 4a and 4b. That was a surprise to me, but consider this:
The equation for a line, such as equation [2], is obtained by subtracting equations like [1a] and [1b].

Let's write the equations for the three circles as:
[a1]     f(x,y) = 0
[b1]     g(x,y) = 0
[c1]     h(x,y) = 0

We get three lines by subtracting:
[a2]     f(x,y) - g(x,y) = 0
[b2]     g(x,y) - h(x,y) = 0
[c2]     f(x,y) - h(x,y) = 0

Note that [c2] is just [a2] + [b2].
A point that lies on the lines [a2] and [b2] (namely at the point of intersection) will also lie on [c2].
Hence that point will lie on all three lines ... implying that all three lines intersect at a single point.

>And that's the point that google maps gives?
I have no idea.


Figure 4a: a perfect world


Figure 4b: reality