|Ivars Peterson's MathTrek|
April 8, 1996
For Christopher C. Chang, a student at Henry M. Gunn Senior High School in Palo Alto, Calif., and one of 40 finalists in this year's Westinghouse Science Talent Search, that demonstration involved soap films and a classic problem invented nearly two centuries ago by Jakob Steiner, a professor at the University of Berlin.
Suppose three cities, Altford, Benford, and Camford, are to be connected by a system of highways. Because the cities are all situated on an unnaturally smooth plain and there are no lakes, hills, rivers, or other obstacles in the region, the builders can put their roads anywhere they wish, so long as they keep the cost (and total length) to a minimum.
In mathematical terms, the problem comes down to finding a new point P such that the total length of the straight lines joining P to each one of three given points, A, B, and C, on a plane has the least possible value. P is known as the "Steiner point."
For the case in which the three cities form a triangle (that is, they're not all in a straight line), the solution involves finding a point inside the triangle toward which straight roads can be built from each city. Using elementary geometry, one can show that the angles between the lines AP, BP, and CP in this simple network all turn out to be 120 degrees.
The Steiner problem can be extended to any number of cities (or points) on a plane and even to situations involving obstacles. In general, given n points, the problem is to find a network of lines that connects all the points and has the shortest total length. For four cities, the solution involves locating two Steiner points, but the angles between the roads arriving at these points remain 120 degrees.
The answer to Steiner's problem can also appear in the shape of a soap film, owing to the fact that the surface tension of a liquid film always acts to minimize the film's area to reach a stable equilibrium.
The experimental solution involves building a plastic frame that consists of a certain number of upright pegs, representing the cities, sandwiched between two transparent parallel plates. When this model is dipped into and then pulled out of a soap solution, the answer is written in the network of planar soap films linking the pegs.
The total area of the soap-film system equals the distance between the two plates multiplied by the total length of the liquid edges along the surface of one plate. Because the soap-film system minimizes area and the distance between the plates is constant, the edges viewed on one plate must minimize length.
The diagram shows the soap-film answer for four cities.
Chang first came across this demonstration several years ago when a speaker described it at a math competition award ceremony. The Steiner problem stuck in his mind, and it eventually became part of his Westinghouse Science Talent Search project.
When Chang started to work on the Steiner problem, he moved it into a different setting. Instead of finding Steiner points on a plane in which roads can go in any direction, he looked for them on a grid, meaning that the roads can go only in certain directions. This put the problem into the realm of discrete geometry.
It's like finding the shortest routes between buildings in New York City, where you have to follow the street pattern. You can't use the Pythagorean theorem to calculate the walking distance between two points. Instead, you can count the number of east-west and north-south blocks that you need to walk and add them together. Distance measurements take on a new meaning.
Without resorting to computers at any stage, Chang began exploring the types of situations that arise for three points on various types of two-dimensional grids, using tools from algebra and calculus to guide his efforts. He quickly found out how difficult the Steiner problem becomes in such a setting.
"Answers to problems often come out much uglier in discrete geometry, since the answer is usually dependent on the precise way distance has been redefined," he notes. "The Steiner point problem with three points, which is a trivial plane geometry problem, becomes enormously complex in discrete geometry, as many close approximations compete to substitute for the simple optimal solution in the Euclidean plane."
Chang discovered that the optimal solution to the Steiner problem typically no longer involves just a single point. That happens only under exceptional circumstances for certain grids. Instead, the Steiner "point" is an entire line segment or a polygon. Thus, the choice of any point within such a polygon or along such a line segment results in the same total distance.
For three given points, the solution polygon is usually an equilateral triangle. If the three given points happen to form a properly aligned equilateral triangle, the solution set for the Steiner polygon is the entire triangle! You can get a sense of how that might happen by considering the different paths you can follow square by square to get from one corner of a checkerboard to the diagonally opposite corner. Without any backtracking, all of these paths have the same (optimal) length. Chang even built a small mechanical model using strings and rods to demonstrate how the choice of starting point within a Steiner triangle makes no difference to the total distance in the three-point case.
Chang speculates that this geometry -- as represented in the Steiner point problem on a grid -- may be applicable to the study of certain interactions in crystals. In a crystal, atoms, ions, or molecules form an orderly array, with a repeating pattern of neat columns and rows. When such a crystal fractures, the cracks tend to follow the directions of the columns and rows, somewhat like a walker sticking to a grid of streets. The shape and size of the Steiner polygon associated with a particular array may have something to say about a crystal's tendency to fracture.
Copyright © 1996 by Ivars Peterson.
Courant, Richard, and Herbert Robbins. What is Mathematics? Oxford University Press, 1941.
Hildebrandt, Stefan, and Anthony Tromba. Mathematics and Optimal Form. Scientific American Library, 1985.
Peterson, Ivars. The Mathematical Tourist: Snapshots of Modern Mathematics. W.H. Freeman, 1988.
Comments are welcome. Please send messages to Ivars Peterson at firstname.lastname@example.org.