Math/Geometry Challenge of the Day

[John Smith]

I picked up a new car equipped with the navigation system. It's a pretty amazing thing -- it always knows where I am, gives me voice directions to reach my destination, and even recognizes my voice. For example, I can say "Go Home" or "Japaneese Restaurants" to the microphone, and it guides me all the way to the corresponding place in a nice soft female voice. As I drive on, the marker on the screen representing my car moves on the map screen, sorrounded by the nicely marked streets, highways, and points of interests (such as ATMs, gas stations, hospitals, parking garages, hotels, etc.)

The way it works is amazing, too. Every one second, three US military satellites transmit signals from the outer space. The signals contain a time stamp and the current satellite location. When the receiver inside my car gets the signal, it compares the current time with the time stamp of the received signal, takes the difference, multiplies it by the speed of light, and viola, it knows how far the car is from the satellite. That's not enough to pinpoint the car location. Since we live in a three-dimensional world, the receiver in the car needs data from three satellites to find that point where the three arcs (representing the distances from satellites) intersect. That point is the car current location. It looks something like this (sorry for the sketchy aspects of it -- it's just a 3-minute pic done with MS Paint):



Now, here is the math challenge of the day. The satellites are carrying atomic clocks, but my car receiver uses a regular clock. The atomic clock is too heavy and too expensive to carry around. Notice, however, that if the clock in my car is off by only 1/10000 of a second, the error in current position location would be 18.7 miles (that's how far the signal travels in 1/10000 of a second), rendering my navigation system useless. But in fact, the accuracy of it is about 50 feet.

Your challenge is to figure out how the receiver in the car can obtain such accuracy with the use of a regular (very imprecise) clock. Hint: it uses the fourth satellite to do that. The fourth satellite does exactly the same thing as the other three satellites -- every one second, it broadcats a time stamped signal that contains the satellite current location. And yes, the problem is purely mathematical.

For the purposes of this homework assignment, don't think in terms of changing speed of light (in vacuum versus the atmosphere) or relativistic effects (yes, the atomic clocks in space run slower than they run on Earth). The computer inside the car does compensate for both effects, but it's irrelevant for the purposes of this problem.
[ February 22, 2005: Message edited by: John Smith ]

[Tarun Sukhani]

Differential GPS
When you measure the distance to four located satellites, you can draw four spheres that all intersect at one point. Three spheres will intersect even if your numbers are way off, but four spheres will not intersect at one point if you've measured incorrectly. Since the receiver makes all its distance measurements using its own built-in clock, the distances will all be proportionally incorrect.

The receiver can easily calculate the necessary adjustment that will cause the four spheres to intersect at one point. Based on this, it resets its clock to be in sync with the satellite's atomic clock. The receiver does this constantly whenever it's on, which means it is nearly as accurate as the expensive atomic clocks in the satellites.

In order for the distance information to be of any use, the receiver also has to know where the satellites actually are. This isn't particularly difficult because the satellites travel in very high and predictable orbits. The GPS receiver simply stores an almanac that tells it where every satellite should be at any given time. Things like the pull of the moon and the sun do change the satellites' orbits very slightly, but the Department of Defense constantly monitors their exact positions and transmits any adjustments to all GPS receivers as part of the satellites' signals.

This system works pretty well, but inaccuracies do pop up. For one thing, this method assumes the radio signals will make their way through the atmosphere at a consistent speed (the speed of light). In fact, the Earth's atmosphere slows the electromagnetic energy down somewhat, particularly as it goes through the ionosphere and troposphere. The delay varies depending on where you are on Earth, which means it's difficult to accurately factor this into the distance calculations. Problems can also occur when radio signals bounce off large objects, such as skyscrapers, giving a receiver the impression that a satellite is farther away than it actually is. On top of all that, satellites sometimes just send out bad almanac data, misreporting their own position.

Differential GPS (DGPS) helps correct these errors. The basic idea is to gauge GPS inaccuracy at a stationary receiver station with a known location. Since the DGPS hardware at the station already knows its own position, it can easily calculate its receiver's inaccuracy. The station then broadcasts a radio signal to all DGPS-equipped receivers in the area, providing signal correction information for that area. In general, access to this correction information makes DGPS receivers much more accurate than ordinary receivers.

GPS Receivers

[John Smith]

The receiver can easily calculate the necessary adjustment that will cause the four spheres to intersect at one point. Based on this, it resets its clock to be in sync with the satellite's atomic clock. The receiver does this constantly whenever it's on, which means it is nearly as accurate as the expensive atomic clocks in the satellites.

That is a good explanation in English. But there is an equivalent mathematical explanation of why at least 4 satellites are required. The challenge still stands.

[Jason Menard]

Moved to Programming Diversions.

[Ryan McGuire]

Why are four satellites needed to define a single point in 3d space when you know only the differences between the distances from the satellites to the point?

In the original diagram the circles around SAT1 and SAT2 intersect at just two points. However, the locus of all points that are a common difference distances from two points is a hyperbola on any plane that includes those two points*. In 3d, the shape is that of a hyperbola rotated around the line between the points -- a hyperbolic cone, if I'm not mistaken*.

There are also hyperbolic cones* defined by the difference in signal travel times between SAT1/SAT3 and SAT2/SAT3. The SAT1/SAT2 h.cone intersects the SAT1/SAT3 h.cone in a closed loop (in 3d)*. That closed loop intersects the SAT2/SAT3 h.cone at two points*.

So a fourth satellite is needed to be the deciding vote between these two points.

Clear as mud?

Ryan

* = This is the general case. If the difference between travel times for the signals between two satellites is 0, then the hyperbolic cone flattens out into a plane. So... if you're really lucky, the differential signal travel times from just three satellites might be sufficient.
[ March 01, 2005: Message edited by: Ryan McGuire ]

[Ryan McGuire]

Perhaps a shorter answer would be that if your car is not on the same plane as the first three satllites, the best they can do designate two possible locations for the vehicle: one above their plane and one below. Then a fourth satellite not on the same plane as the first three is needed to pick one of those two points.

Ryan

[John Smith]

OK people, you got close, but here is the real answer. We have four unknowns: three coordinates and the receiver time. The knowns are the positions of four satellites and the time of their transmission. That gives us 4 equations to solve for 4 unknown quantities. Essentially, the software inside the car uses the regular clock inside just for the initial time approximation. Then iteratively, it will correct that time by tiny increments until the calculated distances from all 4 satellites converge to a single point. In effect, the software calculates not just the position of the car, but the precise current time, as well. The equations look like this:

D1 = SQRT( (x - x1)^2 + (y - y1)^2 + (z - z1)^2 ) + timeError
D2 = SQRT( (x - x2)^2 + (y - y2)^2 + (z - z2)^2 ) + timeError
D3 = SQRT( (x - x3)^2 + (y - y3)^2 + (z - z3)^2 ) + timeError
D4 = SQRT( (x - x4)^2 + (y - y4)^2 + (z - z4)^2 ) + timeError

where

Di is the calculated distance to the ith satellite
(xi,yi,zi) is the known position if the ith satellite
(x, y, z) is the car position
timeError is the car's clock error, expressed in distance units

As can be seen from the equations, there are four unknowns, and four equations, which can be solved (although not directly, but iteratively)
[ March 01, 2005: Message edited by: John Smith ]

[Ryan McGuire]

Originally posted by John Smith:
OK people, you got close, but here is the real answer.
...

You say toMAYto, I say toMAHto.

Ryan