1. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    45044
    16 Oct '13 21:46
    There are n islands, with known coordinates. Let's start with three points, at (0,0), (4,0) and (0,3). The islanders want a network of bridges that allows people to go from any island to any other island, and want to minimize the amount of construction.

    What is the least length of bridge material that suffices for the task?
  2. Joined
    26 Apr '03
    Moves
    25811
    16 Oct '13 22:57
    I'll leave this one for others :-)
  3. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    17 Oct '13 00:30
    Are you saying to start with the three coordinates given (0,0),(0,4),(3,0) and generalize to n random points in R^2?
  4. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    16018
    17 Oct '13 05:00
    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.
  5. e4
    Joined
    06 May '08
    Moves
    25424
    18 Oct '13 15:42
    Phew.....aint got a clue.

    Wait till the tide goes out and just walk between the islands.
  6. SubscriberAThousandYoung
    All My Soldiers...
    tinyurl.com/y9ls7wbl
    Joined
    23 Aug '04
    Moves
    24791
    18 Oct '13 17:59
    Find the center of the triangle. Three roads that go from each node and meet in the center.

    I don't think that can be generalized to n nodes though.
  7. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    19 Oct '13 01:06
    Originally posted by AThousandYoung
    Find the center of the triangle. Three roads that go from each node and meet in the center.

    I don't think that can be generalized to n nodes though.
    The center of the configuration doesn't exist in this case, it is not one of the "n" (in this case 3 Islands). Also, a bridge from the center of the triangle to each vertex is not the minimum material. In the case of the three points, the minimum material that connects all three islands would be 7 units; i.e. a bridge from (0,0) to (0,4) and from (0,0) to (3,0).
  8. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    45044
    19 Oct '13 05:571 edit
    The original was meant to say that this problem can be of course expanded to any number of points and any locations. Ideal would be a generic solution, but it's a bit hard to picture, so a few points it is for now.

    If all points are connected to some point (x,y), whether it be (0,0) or some other point, the total length of the network would be

    sqrt(x^2+y^2) + sqrt((x-4)^2+y^2) + sqrt (x^2 + (y-3)^2)

    Say.. (1,1).. sqrt 2 + sqrt 10 + sqrt 5 < 7

    But is that the best strategy? And if so, the best spot?
  9. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    19 Oct '13 20:522 edits
    As for the best spot;

    If L(x,y) = Sqrt[x² + y²] + Sqrt[(x-4)² + y²] + Sqrt[x² + (y-3)²]

    Then apply the Second Partials Test for relative extrema.
  10. SubscriberAThousandYoung
    All My Soldiers...
    tinyurl.com/y9ls7wbl
    Joined
    23 Aug '04
    Moves
    24791
    20 Oct '13 05:26
    Originally posted by joe shmo
    The center of the configuration doesn't exist in this case, it is not one of the "n" (in this case 3 Islands). Also, a bridge from the center of the triangle to each vertex is not the minimum material. In the case of the three points, the minimum material that connects all three islands would be 7 units; i.e. a bridge from (0,0) to (0,4) and from (0,0) to (3,0).
    That would not allow (0,4) to go directly to (3,0). Of course if you can go through the other points a single road is the optimal solution.
  11. Joined
    26 Apr '03
    Moves
    25811
    20 Oct '13 11:31
    Aha! The point that is the minimum distance from all the other points!

    That is the geometric median.
  12. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    45044
    20 Oct '13 21:321 edit
    "Not by going through another island"
    You could make a tiny road circling around (0,0) at an infinitesimal distance to avoid going actually through that point, and it would not noticeably add to the amount of bridge building. For simplicity, let's say going through another island is permissible.

    "Geometric median"
    I may have misunderstood you (sorry!) but if you meant the point that is as far from each of the three islands, it would be (2,1½ ), which is 2.5 units of length from each island, for a total bridge network length of 3 x 2.5 = 7.5, giving a total bridge network length that is longer than connecting the other two islands to (0,0) ?

    "L(x,y) = Sqrt[x² + y²] + Sqrt[(x-4)² + y²] + Sqrt[x² + (y-3)²]"

    dL/dx = dL/dy = 0 would, I think, give

    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

    Doable with good software for sure, and if L ~ height of a point on a surface it would look quite beautiful. Looks far from trivial from this point on though?
  13. Subscribersonhouse
    Fast and Curious
    slatington, pa, usa
    Joined
    28 Dec '04
    Moves
    52724
    21 Oct '13 22:47
    Originally posted by talzamir
    "Not by going through another island"
    You could make a tiny road circling around (0,0) at an infinitesimal distance to avoid going actually through that point, and it would not noticeably add to the amount of bridge building. For simplicity, let's say going through another island is permissible.

    "Geometric median"
    I may have misunderstood you (sorry!) ...[text shortened]... nt on a surface it would look quite beautiful. Looks far from trivial from this point on though?
    But isn't it just a 3,4,5 triangle? So 5 plus half of 5? 7.5? Hypotenuse line plus a line halfway across the hypotenuse to 0,0?
  14. Joined
    26 Apr '03
    Moves
    25811
    21 Oct '13 23:05
    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)
  15. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    22 Oct '13 00:21
    Originally posted by talzamir
    "Not by going through another island"
    You could make a tiny road circling around (0,0) at an infinitesimal distance to avoid going actually through that point, and it would not noticeably add to the amount of bridge building. For simplicity, let's say going through another island is permissible.

    "Geometric median"
    I may have misunderstood you (sorry!) ...[text shortened]... nt on a surface it would look quite beautiful. Looks far from trivial from this point on though?
    Yeah I agree, its certainly not trivial to apply that method from this point on. However, I suppose the result would be the "Geometric Median" as Imatiger purposed (or the Fermat point in this case) which Wiki claims no explicit formula for its calculation exists.
Back to Top