= 27d567bc2d48d9f40e9ccc20ea370b15)
SarahC comments on Cultivating our own gardens - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (47)
This is correct.
Silas, the problem isn't a perfect match to the actual US -- it assumes straight-line highways, for example.
The graph indeed doesn't have to be planar. We just want to embed it in the plane while preserving distances. And adding nodes does change the problem.
But if all highways are straight, and the graph can have crossovers, doesn't the existing road map already preserve distances, meaning your solution can just copy the map?
I guess I'm not understanding the problem constraints.
The problem is to derive the map, based on the limited set of data you're given. Copying a map would be cheating.
I think you're trying to interpret this as a practical problem of cartography, when in reality its more of a computer sciencey graph theory problem.
You don't have a road map, to start with. You're ONLY given a list of cities and the distances between some of them. From that list, draw a map. That is not a trivial task.
Okay, that makes more sense then. Maybe you should have referred to an imaginary land (instead of the US), so as not to imply people already know what it looks like from above.
Here's an equivalent problem that may make more sense: you have a group of soldiers on a battlefield without access to GPS equipment, and they need to figure out where they are in relation to each other... they each have radios, and can measure propagation latency between each other, telling them linear distance separating each of them, but telling them nothing about directionality, and from that data they need to construct a map of their locations.