3
$\begingroup$

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?

  • 0
    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. http://sauk.wisgop.info/files/2010/08/interstate.gif2011-11-25

0 Answers 0