Island Bridges

Originally posted by iamatiger
With the triangle
(0,0), (4,0) and (0,3)
The point
0.75, 0.7 is interesting

distance from 0,0 = 1.03
distance from 4,0 = 3.38
distance from 0,3 = 2.36

total material needed = 1.03 + 3.38 + 2.36 = 6.77

so, although this is not the absolute best point it shows we can obviously do quite a bit better than building straight roads from 0,0 to the other two points (which takes 7 units)

Yeah, I see that now. Talzamir, also pointed that fact out to me in an earlier post.

We can get a general solution for 3 towns, but I think a general solution for N towns is going to be impossible! Consider 4 towns in a tall thin rectangle, it is fairly easy to see that we will need roads in the shape of a capital I, maybe pointing the ends up a bit, which is has two non-town junctions rather than 1.

Taking Talz's equations:

x / Sqrt[x² + y²] + (x-4) / Sqrt[(x-4)² + y²] + x / Sqrt[x² + (y-3)²] = 0
y / Sqrt[x² + y²] + (y-3) / Sqrt[x² + (y-3)²] + y / Sqrt[(x-4)² + y²] = 0

To save chars let us define:
A = Sqrt[(x-4)² + y²]
B = Sqrt[x² + (y-3)²]

so
x / Sqrt[x² + y²] + (x-4) / A + x / B = 0
y / Sqrt[x² + y²] + (y-3) / B + y /A = 0

((x-4) / A + x / B)/x = 1/ Sqrt[x² + y²]
((y-3) / B + y /A)/y = 1/ Sqrt[x² + y²]

((x-4) / A + x / B)/x = ((y-3) / B + y /A)/y

(x-4)/(Ax) + 1/B = (y-3) /( By) + 1/A

multiply out the brackets
1/A - 4/(Ax) + 1/B = 1/B- 3/(By) + 1/A

cancel out similar terms

4/(Ax) = 3/(By)

May be progress? We can get 1/B in terms of 1/A
have to go to work now

Screw those Bas****ds over there.

All the beer and naked women are on this island. 🙂

Consider any rectangle.. would it be a capital I, or H, or more like the Pisces horoscope symbol? Even a U shape, with one long end and two short ones, would give the same result total length. But clearly it is not applicable when you approach a square. But is the answer for a cross an X in the middle, or the pisces?

Actually, the rectangle is not that bad if the pisces shape works?

And the second solution only works if all the beer, all the women, and *all the boats* are on this island. 😉

seems clear that a tall thin rectangle must be like a capital I, possibly with the junctions shrunk slightly in towards the end, or maybe with a long diagonal and two short branches off to the corners... either way it is topologically different from the solution for the triangle, and a general solution for all networks seems extremely unlikely.

Starting with something that seems clear.. an equilateral triangle ABC. It would see that then a Y shaped bridge is ideal, the crossroads at the middle of the triangle.

What happens when point B is moved towards AC along the perpendicular to AC? The triangle ABC becomes an isosceles triangle, but does the ideal spot for the crossroads move in the same direction or B or towards B, or not at all?

That should shed some light, expanding from one triangle to a whole group of them.

And then, when B has been moved, if C moves too we get the rest of the triangles.. and can even assume that C also moves perpendicularly or parallel to AB. That gives the remaining triangles. And actually might shed some light about what happens when there are four points or more?

For the original island triplet the best place for the crossroads seems to be about (.752; .696) which gives a total bridge length of 6.766.

For a long thin rectangle of (+/- 5, +/- 1) the optimal seems to be to use two intersections, at (+/- 4.423 , 0) and a total bridge length of 13.464.

An even longer and thinner rectangle of (+/- 500, +/- 1) gives the intersection points (+/- 499.423, 0) and a total bridge length of 1003.464.

All examples done with excel using a monte carlo method and some thousands or tens of thousands of iterations, not really very advanced math.

Originally posted by forkedknight
My strategy would be to start with the shortest possible path between any two nodes, and build the first bridge there.

Then, find the next shortest path between any two nodes, if those nodes are not connected by some other route, build a bridge between them.

Repeat until all nodes are connected to the network.

A bit late to the party, but your answer is pretty close to the correct one. In fact, the original problem is a "Minimum Spanning Tree Problem" and is fairly well known. The correct algorithm is indeed to.

1. Find the shortest distance between any two islands and build a bridge there.
2. Find the unconnected island closest to any of the already connected islands and build a bridge to that one. Repeat until all islands are connected. (In case of ties you can pick any of the shortest distances)

Originally posted by Barts
A bit late to the party, but your answer is pretty close to the correct one. In fact, the original problem is a "Minimum Spanning Tree Problem" and is fairly well known. The correct algorithm is indeed to.

1. Find the shortest distance between any two islands and build a bridge there.
2. Find the unconnected island closest to any of the already connected i ...[text shortened]... at until all islands are connected. (In case of ties you can pick any of the shortest distances)

That's is correct, except in this question we can build new islands (at useful points) which makes it a *lot* more complicated.