|
|
|
|
|
|
|
|
|
Building a Bridge: What is this about?
|
| Buy this applet |
This one is a basic optimization problem. It's well known and serves as an easy illustration of the usefulness of the simplest of geometric transforms - translation.
| Two points A and B are given on opposite sides of a strip defined by two parallel lines. The strip represents a river, and the points to cities on the opposite sides of the latter. The problem is to build the shortest possible road between A and B, assuming that the land parts of the road are straight line segments and the bridge is perpendicular to the banks. |
Let C be a point on the upper bank and C' its mate on the lower bank, so that CC' is perpendicular to both lines. CC' defines a vector V and a translation transform in the plane. It is clear that the length of V enters all possible choices of C on the upper bank. The problem is thus equivalent to minimizing the "land" sum
Translate point B by -V to obtain B'. By the triangle inequality,
AC + CB'  AB',
|
while CB' = C'B. Therefore, the shortest route is defined by the position of C where the line AB' crosses the upper bank.
Clearly, we could have translated A by V to A' and considered intersection C' of A'B with the lower bank. The result would have been the same.
References
- I. M. Yaglom, Geometric Transformations I, MAA, 1962
| 28733128 |  |
|