What Gauss was discussing was the Steiner problem for four points. In a letter to the Danish-German astronomer Christian Schumacher that year, he wrote: “I have on occasion considered the railway connection between Harburg, Bremen, Hannover and Braunschweig.” At that time, no such railways existed, so he was anticipating the theoretical challenge of constructing optimal networks. These points are of degree three: three line segments meet at each Steiner point at angles of 120°.Ĭarl Friedrich Gauss looked at the Steiner problem in 1836. He showed that if there are n given points, no more than n – 2 Steiner points are needed to achieve a minimum. Gergonne later posed the problem in more abstract terms: Connect any number of given points by a system of lines whose total length is as small as possible. This is the first known statement of the Steiner tree problem. He expressed it thus: A number of cities are situated at known locations in the plane the problem is to link them together by a system of canals whose total length is as small as possible. In addition to the Fermat-Torricelli problem, Gergonne analysed a number of generalisations. If an angle of the triangle equals or exceeds 120°, then the two sides adjacent to this angle provide the minimal network there is no need for an additional (Steiner) point. These lines cross at a point that provides the solution, as shown here: He constructed equilateral triangles on two sides of the triangle, and joined the additional vertex of each to the opposite vertex of the original triangle. Torricelli found that, if no angle of the triangle linking the three points is greater than 120°, the solution is a point such that the three lines from this point to the vertices meet at angles of 120°. This problem was originally posed by Pierre de Fermat in 1643 in a letter to the Italian physicist and mathematician Evangelista Torricelli. Put another way, given three points in a plane, find a fourth such that the sum of its distances from the first three is as small as possible. This asks for the shortest network connecting three points in the plane. Gergonne first considered the Fermat-Torricelli problem, one of the simplest network minimisation problems. They point out that the first person to pose and analyse the problem was the French mathematician Joseph Diaz Gergonne (1771-1859). A comprehensive history of the Euclidean Steiner tree problem was published recently by Brazil et al. The problem is relevant for applications in many areas, including communications, power grids, transport networks, electric circuit layout, facility location, pipeline networks and the efficient design of microchips.Īlthough the problem was analysed by Jakob Steiner, he was not the first person to consider it. The problem we now call Steiner’s problem was originally posed in purely geometric terms, but its solution involves mathematical techniques from combinatorics, analysis and computational science. Born near Berne, he moved to Germany in 1818, and spent most of his life in Berlin, where he was on friendly terms with Jacobi and Abel. Jakob Steiner (1796-1863) a Swiss mathematician, was one of the greatest geometers of all time. A solution of Steiner 5-point problem with soap film.
0 Comments
Leave a Reply. |