building a bridge

[BMAD]

Suppose we have to build a road from city A to city B, but these cities are separated by a river (straight, consistent width). We would like to minimize the length of the road between these cities and the bridbe must be constructed perpendicular to the banks of the river. Where to build the bridge as to minimize the total length of the road?

I know two different ways to solve this problem. Can you find both?

[Anza Power]

Imagine that the river is on the x axis and A and B are some dots below and above it, since the river width is consistent you can assume we already paid for the bridge and eliminate the river, as in make it's width 0, and now the shortest distance is a straight line

Well, except that we are given the river as is, with a fixed width and a bridge perpendicular to its flow.

We do not know whether the line joining the cities lines up with the bridge - a very special case with a trivial solution.

We also do not know that the cities are equidistant from the river - a fact that bears on bridge placement if is not parallel to the joining line.

I'm curious to know the two different ways BMAD has to optimize the bridge placement.

You might've misunderstood me a little bit, I should have detailed a bit more, let the river be of width 1 unit, align the axis such that the x axis is parallel with and centered the river, in other words the river would be the area -0.5<y<0.5, now "removing" the river means collapsing it and so every point that was below it now goes up by 0.5 units and every point above it goes doen 0.5 units...

[bonanova]

The easiest solution is to argue that the middle of the bridge should be on a straight line joining A and B. By symmetry the road length will be an extremum. Moving the bridge one way or the other by a short distance will increase (or decrease) the road length, whichever way it's moved. And, by moving the bridge a great distance from the center line it's clear the change will be an increase.

But it's also a nice exercise to put the bridge at an arbitrary position and the river at an arbitrary angle and show that for any river angle the road length is minimized when the roads leaving A and B make the same deviation to the left (or right) from the center line.

Edit: Except it's more complicated. The above statement is true only if the midpoint of the bridge can be placed on the midpoint of the joining line. But of course that cannot be guaranteed. We are not free to move the river. Back to the drawing board.

Edited September 23, 2013 by bonanova
Further thought

[Anza Power]

Imagine that the river is on the x axis and A and B are some dots below and above it, since the river width is consistent you can assume we already paid for the bridge and eliminate the river, as in make it's width 0, and now the shortest distance is a straight line

[plasmid]

Are you sure about that?

Consider the scenario where the river does not lie halfway between city A and city B. In fact, suppose it lies right next to city A and is at a 45 degree angle. A drawing would help.

If the center of the bridge lies on the line from A to B, then you follow the solid line. If the start of the bridge lies at the city gates of A, then you follow the dot-dash line.

If you were to make city A very small (unlike in the drawing), and you omit the potions of these paths that cross over the bridge (because they will be the same length on the two paths), it should be clear that you could move that bit of the solid line from city A to the bridge up so it would connect the end of the solid line from city B to the bridge and the end of the dot-dash line from city B to the bridge so they form a triangle. And it will then be instantly obvious that the dot-dash path is shorter than the solid line path.

I started trying to do the math to solve for the distances explicitly, and it looks too hard for me.

Edit: Saw that Bonanova edited. And:

I have a feeling that one might want to place the bridge such the path from A to the bridge and the path from B to the bridge are parallel. The hand-waving explanation is that then joining the two lines from A to the bridge and B to the bridge would create a straight line, as opposed to a triangle in the example above.

Edited September 24, 2013 by plasmid

[bonanova]

Imagine that the river is on the x axis and A and B are some dots below and above it, since the river width is consistent you can assume we already paid for the bridge and eliminate the river, as in make it's width 0, and now the shortest distance is a straight line

Well, except that we are given the river as is, with a fixed width and a bridge perpendicular to its flow.

We do not know whether the line joining the cities lines up with the bridge - a very special case with a trivial solution.

We also do not know that the cities are equidistant from the river - a fact that bears on bridge placement if is not parallel to the joining line.

I'm curious to know the two different ways BMAD has to optimize the bridge placement.

[bonanova]

Are you sure about that?

Consider the scenario where the river does not lie halfway between city A and city B. In fact, suppose it lies right next to city A and is at a 45 degree angle. A drawing would help.

Towns and bridge.jpg

If the center of the bridge lies on the line from A to B, then you follow the solid line. If the start of the bridge lies at the city gates of A, then you follow the dot-dash line.

If you were to make city A very small (unlike in the drawing), and you omit the potions of these paths that cross over the bridge (because they will be the same length on the two paths), it should be clear that you could move that bit of the solid line from city A to the bridge up so it would connect the end of the solid line from city B to the bridge and the end of the dot-dash line from city B to the bridge so they form a triangle. And it will then be instantly obvious that the dot-dash path is shorter than the solid line path.

I started trying to do the math to solve for the distances explicitly, and it looks too hard for me.

Edit: Saw that Bonanova edited. And:

I have a feeling that one might want to place the bridge such the path from A to the bridge and the path from B to the bridge are parallel. The hand-waving explanation is that then joining the two lines from A to the bridge and B to the bridge would create a straight line, as opposed to a triangle in the example above.

I agree. And my edit was meant to debunk my first notion.

I did the calculation for three bridge placements in the (easiest) case of placing A on the river's edge, very similar to your drawing. The three placements had the east end, the west end and the middle of the bridge on the joining line. My code for the middle placement had an error, but it was clear that that case would not minimize the road length - the east-end placement was going to be the best of the three.

The considerations I posted above to AP come into play, and I agree the general case is far from trivial -- both to calculate and to optimize. I think it can be done, but I put it away last night for possibly another time.

[BMAD]

Denote one town as A and the other as B and the bridge on A's side be P and the bridge on B's side be Q.

Then the roads will be AP, PQ, and QB.

The goal of course is to optimize the combined length of these three roads. Since the river width is constant, notice that PQ is always constant regardless of where it is placed. The more complicated solution i hinted at utilizes trignometry.

We can assume some coordinates (Xa, Ya) and (Xb, Yb) for cities A and B respectively. We can build a formula for the length of the connection between cities A and B that is a function of an angle r and find the minimum length.

I will let the readers continue down this path if they desire the more complicated solution.

Of course there is a much easier solution that doesn't require any trignometry. Can anyone reason it?

[plasmid]

Ah, I understand Anza's answer better now. If you actually do "warp the map" by cutting out the river completely and dragging the two halves of land together and stitching them up, then drawing a straight line over the remaining land would give you the shortest path (excluding the bridge), and the point at which that line crosses the scar left by the removed river would tell you where the bridge should be. That as well as the spoiler in my post above should, I think, qualify as two ways to go about it without the hard math. Anza's approach is better because it would tell you exactly where to place the bridge, not just tell whether or not you've found the best spot and which way to nudge the bridge if it's not optimally placed.

[BMAD]

Yes. Anza identified the easier method