Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I'm building n highway system for $N$ cities on a Euclidean plane. I want to minimize the ratio of the average highway distance between each pair of cities, i.e. $\sum_{i \in P, j \in P} \| i - j \| / N^2$, divided by the total length of the roads. Is there a method for creating these paths which gives the least of this ratio?

share|improve this question
    
I don't see how the randomness enters into the question. Would the answer be any different if you left out "randomly distributed"? Also, you haven't said anything about the sorts of highways that are allowed. Can we only connect pairs of cities directly, or could we also join more than two of them with additional vertices in between? In either case, I wouldn't expect there to be a simple answer. –  joriki Nov 25 '11 at 5:36
1  
This sounds like a variation on the Travelling Salesman Problem. Read about it here: en.wikipedia.org/wiki/Salesman_problem –  WesT Nov 25 '11 at 6:02
    
Yes, additional vertices are allowed, and I have removed "randomly distributed." If the points were large cities in the United States, the result would look something like this. sauk.wisgop.info/files/2010/08/interstate.gif –  Vortico Nov 25 '11 at 7:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.