For Christopher C. Chang, one of 40 finalists in the 1996 Westinghouse Science Talent Search, that demonstration involved soap films and a classic problem devised nearly two centuries ago by Jakob Steiner, a professor at the University of Berlin. Chang was a high school student when he undertook the mathematics project that brought him to the prestigious national competition.
Suppose three cities, Altford, Benford, and Camford, are to be connected by a system of highways. Also suppose the cities are all situated on an unnaturally smooth plain and there are no lakes, hills, rivers, or other obstacles in the region. Hence, the builders can put their roads anywhere they wish, so long as they keep the cost (and total length) to a minimum.
One possibility is to connect the cities with two roads. However, it turns out that the connecting roads have a shorter length if there is a "phantom city" or a crossroads in the middle to which the three cities are linked.
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 of the given points, A, B, and C, on a plane has the least possible value. P is known as a Steiner point,
If the three cities form a triangle rather than a line, the solution involves finding a point inside the triangle toward which straight roads can be built from each city. Using elementary geometry, you can show that the angles between the lines AP, BP, and CP in this simple network all turn out to be 120 degrees.
Chang first came across this demonstration when a speaker described it at a mathematics 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 from one building to another in New York City, where you have to follow a grid-like street pattern. Rather than using the Pythagorean theorem to calculate the walking distance between two points, you must count the number of east-west and north-south blocks that you need to walk and add them together. Route distances take on a new meaning.
Using tools from algebra and calculus to guide his efforts, Chang began exploring the sorts of patterns that arise for three points on various types of two-dimensional grids. He quickly saw 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," Chang noted. "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 involves more than just a single point. A single-point solution happens only under exceptional circumstances for certain grids. In most cases, however, 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 an appropriately aligned equilateral triangle, the solution set for the Steiner polygon is the entire triangle!
To get a sense of how that might happen, consider 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 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 speculated that the geometry 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 likelihood of fracturing.
Steiner problems can be generalized to situations in which the goal is to connect a given collection of points with a network of the shortest possible length. With all points connected, such a network is called a minimum spanning tree.
Such problems arise in the design and analysis of telecommunications and oil pipeline networks, determination of relationships among different species from sequences of amino acids in proteins, laying out components on computer chips, and other applications.
Originally posted April 8, 1996
Suppose three cities, Altford, Benford, and Camford, are to be connected by a system of highways. Also suppose the cities are all situated on an unnaturally smooth plain and there are no lakes, hills, rivers, or other obstacles in the region. Hence, the builders can put their roads anywhere they wish, so long as they keep the cost (and total length) to a minimum.
One possibility is to connect the cities with two roads. However, it turns out that the connecting roads have a shorter length if there is a "phantom city" or a crossroads in the middle to which the three cities are linked.
The shortest route joining A, B, and C is not the one that connects the three points (left) but one that passes through a point P (right).
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 of the given points, A, B, and C, on a plane has the least possible value. P is known as a Steiner point,
If the three cities form a triangle rather than a line, the solution involves finding a point inside the triangle toward which straight roads can be built from each city. Using elementary geometry, you 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 not on a single line, 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 are all 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 configuration.
The experimental, physical solution involves building a plastic frame that consists of a given 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.
Soap-film solution of Steiner's problem for five points (left) and four points (right).
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.
Chang first came across this demonstration when a speaker described it at a mathematics 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 from one building to another in New York City, where you have to follow a grid-like street pattern. Rather than using the Pythagorean theorem to calculate the walking distance between two points, you must count the number of east-west and north-south blocks that you need to walk and add them together. Route distances take on a new meaning.
On a grid of squares, the distance between two points, A and B, is the sum of the vertical and horizontal steps required to travel the route.
Using tools from algebra and calculus to guide his efforts, Chang began exploring the sorts of patterns that arise for three points on various types of two-dimensional grids. He quickly saw 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," Chang noted. "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."
For three given points, A, B, and C, on a grid of squares, introducing the point P minimizes the total length of the path connecting all three points.
Chang discovered that the optimal solution to the Steiner problem typically involves more than just a single point. A single-point solution happens only under exceptional circumstances for certain grids. In most cases, however, 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 an appropriately aligned equilateral triangle, the solution set for the Steiner polygon is the entire triangle!
To get a sense of how that might happen, consider 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 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 speculated that the geometry 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 likelihood of fracturing.
Steiner problems can be generalized to situations in which the goal is to connect a given collection of points with a network of the shortest possible length. With all points connected, such a network is called a minimum spanning tree.
Such problems arise in the design and analysis of telecommunications and oil pipeline networks, determination of relationships among different species from sequences of amino acids in proteins, laying out components on computer chips, and other applications.
Originally posted April 8, 1996
No comments:
Post a Comment