= 27d567bc2d48d9f40e9ccc20ea370b15)
Sniffnoy 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)
I also am confused by the metaphor; however it's worth noting is that the problem is not to embed a graph in the plane without crossings, but rather to embed a weighted graph in the plane (possibly with crossings) such that the distances given are equal to the Euclidean distances from the embedding. And adding nodes would be changing the problem, no?
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.
It depends on whether the US cities bit was just an illustrative example, or a typical constraint on the problem.
Does the problem take for granted, e.g., that roads can be winding so that the weight necessarily does not equal the Euclidean distance (Riemannian distance, really, on a curved paper, but whatever), and you have to make a planar map that locates the nodes so that the weight is (proportional to) the Euclidean distance?
I don't see how this is relevant to the statement that adding nodes would be changing the problem. You're given a specific graph of distances, the challenge is to realize it in the plane. You can't just add nodes and decide to realize a different graph in the plane instead; where would the distances even come from, anyway, if you haven't yet computed an embedding?
SarahC cleared it up, so I understand what you do and don't know in the problem, and why I assumed certain things were given that aren't.
Though I agree with Roko's comment that this doesn't seem to provide insight on resolving ethical differences.