3 ms·
I submit this for a few reasons. The first is that when I use SatNav I arrive at my destination having no real idea where I am. I remember in a science fiction
by RiderOfGiraffes 17y ago
I submit this for a few reasons.
The first is that when I use SatNav I arrive at my destination having no real idea where I am. I remember in a science fiction book reading a statement like "We claim to have explored space, but in truth, we have explored the small bubbles that surround individual planets. Of the great depths of true space we have no knowledge." I feel a little like that now when driving longer distances with the SatNav.
Secondly, it's interesting how often the SatNav produces "obviously" sub-optimal routes. The Travelling Salesman Problem is well-known to be NP-Complete, so it's not surprising, but some of the foibles are incomprehensible. It's no wonder some people distrust them, and quite surprising that others seem to have complete faith in them.
Finally, stop for a moment to consider the miracle that is the modern SatNav. Despite its short-comings it contains a device to tell you where you are to within a fathom, maps that know where you are and where you're going, enough power to compute a sensible (if not always optimal!) route between the two, a suer interface that non-technical people can usually drive, and all for the cost of a few hours work.
Addendum: GPS works by computing varied flight times of radio pulses. Light travels about a foot per nano-second, so a GPS receiver has to work with time differences less than a typical clock cycle (for the on-board computer). If you have a 1GHz computer, light cannot travel across the motherboard in a single clock-cycle.
Stunning.
PS: Yes, I do know the details, and I know the inaccuracies in the above.
- wlievens 17y agoWhat does the Traveling Salesman Problem have to do with typical GPS navigation? Typical use of a GPS device involves a start and an end point, and every once in a while a couple points in between, that ideally you may want in optimal order (though I doubt typical devices can do that for you). But there's nothing intractable about the scale of that.
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- RiderOfGiraffes 17y agoSorry, you're right. My recent work has involved pathological cases of dynamic spanning trees, and I've recently proved that a sub-class is NPC, and I mis-spoke myself here. The SatNav problem is obviously easier. Given the power of the processor, limited memory, and complexity of streets (in the places I typically deal with) I still find it surprising. But you're right. Dijkstra's algorithm clearly solves this problem simply enough in O((|E|+|V|) log |V|) for the sparse case. Apologies.
- baha_man 17y agoInteresting article, but I didn't follow the 'destroying local knowledge' part. "Since before even the arrival of the car, people have worried that maps sever us from real places, render the world untouchable, reduce it to a bare outline of Cartesian lines and intersections." I've never heard this before.
- jerf 17y ago"The first is that when I use SatNav I arrive at my destination having no real idea where I am." Then you're doing it wrong. Using a SatNav system has taught me a lot about my local area. Since my wife got her system, I've found three or four new routes just in my city. (Well, city-let, it's no New York.) They aren't all great, but they work and I didn't know that. (And it's not even my device; I don't drive with it all the time.) Maybe you need to switch to map view and zoom out a step or two. It's like having psychic knowledge of roads you can't see and never would have normally gone down.