Thursday, August 6, 2015

Minimizing Length to a Segment, Cont'd

Place a segment of length 1/2 in such a way as to minimize the sum of its distances to three vertices of a unit square.


In the example shown, the three lengths to be added are shown as dashed lines. (The example shown is not optimal.)

I didn't know how to solve this puzzle when I posted it, but since then I have thought about it some, and I think I have the answer.

Here goes; if I have it wrong, someone will let me know.

To begin with, replace the dashed lines in the figure with solid lines. The result is a network that connects the three vertices of the square. Obviously, this network cannot be shorter than the shortest possible network connecting the three vertices. But what is the shortest possible network connecting three points?

As I learned from this historical study, Pierre de Fermat first posed a similar problem in 1643:
datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minima quantitatis.

Apparently this is Latin for
given three given points, a fourth is to be found, from which if three straight lines are drawn to the given points, the sum of the three lengths is minimum.
Fermat himself could probably solve this problem, but the first known solution is due to Torricelli (1608–1647). Then, it seems, the problem was forgotten until it was posed again in 1810 by the French mathematician Joseph Gergonne. He posed a number of extensions of the problem, including some that resemble our segment problem. 

Gergenne was the first to pose what has become known in modern times as the Steiner tree problem: Given a collection of points in the plane, find the shortest network that connects them. This is the problem we are interested in today. The Steiner problem differs from Fermat's problem because Gergenne isn't assuming from the outset that the network will meet in a single point (though that turns out to be the case for three boundary points).

Gergenne solved the problem in some specific cases and made impressive progress toward general conclusions. Later, Gauss toyed with the problem, and a mathematician/schoolteacher named Bopp did further work on it, including deriving the first results for a collection of boundary points in three-dimensional space. 

In the 1930's, a couple of Czech mathematicians gave the first modern treatment of the Steiner problem, and in the 1960's interest in the problem exploded. The reason seems to have been twofold. First, problem was presented to a wide readership in the popular 1941 book What Is Mathematics? (still popular!); and second, the problem proved to be directly related to emerging industrial problems such as optimizing integrated circuits and communication networks.

Today, it is known that length-minimizing networks in the Euclidean plane always consist of straight segments that meet in threes at angles of 120 degrees. Like other optimal forms, these minimal networks are often handsome to look at.

(By the way, I first learned about all this when I was an undergraduate and part of the group that proved the planar double-bubble conjecture.)

So much for the history. How does this knowledge help us in the segment problem? Recall that we were interested in the shortest possible network connecting three vertices of the unit square. Based on the summary above, you can probably devise this network yourself; it looks like this:




This length-minimizing network provides a way to solve our segment problem: namely, we lay down our segment along one of the edges of the minimal network:




If we denote the length of the minimal network by L, then we see that the dashed segments in this solution have total length L - 1/2. There is no way to give the dashed lines a smaller total length. For if you could somehow connect the three vertices to the segment using total length D < L - 1/2, then there would exist a network of length D + 1/2 <  L. Since no network exists with length less than L, no better solution to the segment problem exists either.

By the way, our solution has a total dashed length of about 1.43. By comparison, laying the segment vertically down the left-hand edge of the square (touching the upper-left vertex) gives a total dashed length equal to 1.5.

No comments: