Originally posted by luskinYeah, I think Steiner tree constructions are kinda cool. I thought of this question because I was reading the following paper which has some background on known-to-be-optimal (minimum) Steiner trees for different nxn arrays: "Steiner Trees on a Checkerboard," F. Chung, M. Gardner, and R. Graham, Mathematics Magazine 62(2), 1989, pp. 83-96.
Very interesting. Never come across that before.
The minimum tree looks pretty cool for a chessboard (treating, say, the center of each square as one point of an 8x8 array; or you could treat all the square corners as points within a 9x9 array).
Originally posted by AThousandYoungThe Steiner tree is very interesting. But it seems to me that if the problem were: how to get to all three cities travelling the minimum length of road that the answer would be 3. The Steiner solution is interesting but leads to inefficient use of time and fuel.
3. A road from A to B, one from B to C, one from C to D.
Originally posted by thymeBut once you factor in the cost of road building...
The Steiner tree is very interesting. But it seems to me that if the problem were: how to get to all three cities travelling the minimum length of road that the answer would be 3. The Steiner solution is interesting but leads to inefficient use of time and fuel.