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.
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.
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.
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.
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.