A.O. Ivanov,
Moscow State University, Moscow, Russia
aoiva@mech.math.msu.su
Contents
The aim of the present article is to demonstrate by an example how mathematicians use in their work the facilities of Computer Geometry and Visualization. The idea of this article has appeared after the talk the authors gave at the Seminar of Consortium “Geometrical Education in New Information Technologies”, one of the Consortium aims is to form contacts between specialists in Computer Graphics and Visualization on the one hand, and mathematicians on the other hand. We use this opportunity to thank all the participants of Seminar for their interest and useful discussion.
The main work of mathematicians is to think out and to verify new conjectures concerning some non-trivial relations between the mathematical objects they are studying. Unfortunately, only few of such conjectures turn out to be true and become Theorems. Lately, to verify the current conjecture, mathematicians more and more often use a computer, more precisely, use a computer experiment. A good constructed and visualized computer model often gives an opportunity either to find a contrary instance to the conjecture in hand, or to detect a way for formal mathematical proof of the conjecture. Here the negative result, i.e. the contrary instance found, is also very useful, since it gives an opportunity for much more deep understanding of the problem considered and for stating a new more reasonable conjecture. Here we give a diagram of this process.
We illustrate it by example of a real problem appeared under investigation of classical Steiner Problem of finding planar trees with a given boundary having minimal possible length, see definition below.
Steiner Problem lies at the meeting-point of Geometry, Graph Theory, and Calculus of Variations, and gives a classical example of a geometrical optimization problem. The history of variational calculus and optimization theory goes back to the works of P.-L.M. Maupertuis (1698-1759), who formulated the famous Least Action Principle: “When a change occurs in nature, the quantity of action necessary for this change is least possible”. However, first of all Maupertuis proceeded from the concept of God perfection, Who, as Maupertuis thought, created the Optimal Universe. First mathematical works investigating optimization problems belong to Leonard Euler (1707-1783). Euler was first who showed that the trajectory of a point mass in a potential force field minimizes the integral of the difference between its kinetic and potential energies. Thus, Euler firstly represented solution of a mathematical problem as a critical point (minimum) of an appropriate variational functional (so-called Euler-Lagrange functional).
Notice that the contemporaries of Maupertuis already understood: “maximums” are as interesting as “minimums”. The well-known example of d’Arci published in 1749 is depicted in Figure.
Fig1 Shows us the concave mirror and the convex mirror.
D’Arci suggested to consider the pass of light emanated from the point A, reflecting from the spherical mirror at the point C and coming to the point B, see Figure. In the both cases the points A and B lie in focuses of the ellipse touching the spherical mirror. It is easy to see, that in the case of the convex mirror (right) the light passes by the shortest trajectory, but in the case of the concave mirror – by the longest trajectory. So the nature is not necessary economical, it also can be prodigal.
Recall that besides local minimums and local maximums functions can have other critical points – so-called saddle points. It turns out that saddle points of functionals also appears as solutions of mathematical and physical problems. To illustrate this fact let us turn to a well-known example – soap films. A soap film appearing at a wire frame evoked from a soap solution tends to minimize its surface tension, which is proportional to the area of the film. Therefore, soap films are a physical model of minimal surfaces – the extremals of the surface area functional. As a rule, the soap films correspond to stable minimal surfaces representing local minimums of the area functional. Sometimes however, using some accurate experiments, one can manage to observe unstable minimal surfaces corresponding to saddle points of the area functional. In Figure below two minimal rotation surfaces – catenaries, spanning the same wire frame consisting of two circles. At the left the stable catenary corresponding to a local minimum of the area functional is depicted, and at the right – the unstable catenary corresponding to a saddle point of this functional.
Fig2.
Steiner Problem was named for Jacob Steiner (1796-1863), a professor at the university of Berlin. In the classical form, the problem is to find the shortest network Г (i.e. a connected planar graph), connecting a given finite set M of plane points. The set M is usually called the boundary set or simply the boundaryр. It is easy to understand, that a solution of Steiner problem is a tree, and this tree is called Steiner minimal tree (for the given boundary set). Below in Figure we give an example of a boundary set and a corresponding Steiner minimal tree.
Fig3.
As is often the case, Steiner Problem has no concern with Jacob Steiner. The above state of the problem appeared essentially after Steiner, in 1934, in the works of Czech mathematicians Jarnik and Kossler. On the other hand, the history of optimization problems of this type goes back to Fermat, 17th century, who suggested to his students the following question: for three given plane points A, B, and C, find in the plane a point S, the sum of whose distances from A, B, and С is minimal. First solution was found by Torricelli, who suggested the folowing construction. Let us construct on the sides of the triangle ABC three equilateral triangles outside the trangle, see Figure.
Fig4.
Circumscribe circles around each triangle constructed. Then, Torricelli asserted, these three circles intersect at the single point S, that solves the Fermat problem. The intersection point of these circles is often called the Torricelli point. Notice that the Torricelli point is a solution of Fermat problem only providing all the angles of the triangle ABC are at most 120 degrees. If one of the angles of the triangle concidered, say B, is more than or equal to 120 degrees, then the solution of Fermat problem is the point B.
Fig5.
Slightly later, Cavalieri found an important property of the Torricelli point S. Namely, if this point lies inside the triangle ABC (and gives the solution to Fermat problem), then the straight segments AS, BS, and CS connecting S and the vertices of the triangle meet each other by equal angles (and, hence, the angles are equal to 120 degrees).
After a century Simpson suggested another way of Torricelli point construction. Again, let us consider a triangle ABC in the plane, and let us assume that all its angles are less than 120 degrees. As above, let us construct the equilateral triangles on the sides of the triangle ABC outside the ABC, and by A’, B’, and C’ we denote the additional vertices of these triangles, see Figure.
Fig6.
Let us draw the straight segments AA’, BB’ и CC’. Simpson proved that these three segments intersect at the Torricelli point. Moreover, the lengths of these segments are the same and are equal to the length of the minimal network, i.e. |AA’| = |BB’| = |CC’| = |AS| + |BS| + |CS|. Each of the segments constructed is called a Simpson line. Later, this Simpson construction was generalized by Melzak, who in 1960 suggested a general algorithm finding Steiner minimal trees, see below.
As Classical Steiner Problem, so as its different generalizations have great importance for applications. The most evident application is transportation problems. Assume that we need to construct a transportation network connecting a given set of settlements. And naturally we want to minimize the expenses. If we assume that the costs of the communications are proportional to their length, then we obtain Classical Steiner Problem, where the boundary set is the set of our settlements, and Steiner minimal tree is the transportation network looked for. Such a network (an approximate solution) joining the first-rate towns in the USA is shown in Figure.
Fig7.
Such networks are used to calculate federal rates for long-distance calls in the USA (the cost of the call is proportional to the length of the path in such a tree joining the terminals).
Another well-known application of generalized Steiner problem is connected to chip design. Since the conductors in such chips are usually of two mutually perpendicular directions in this case one can use so called Manhattan distance instead of the usual length functional. Namely, let us fix an orthogonal coordinates OXY in the plane. Then the length of a straight segment is calculated as the sum of the lengthes of its projections onto the coordinate axes. The corresponding rectangular Steiner problem is to find a network joining given boundary set and having the least possible Manhattan length. It is not difficult to show (Hanan) that ion this case there exists a minimal tree all whose edges are parallel to the coordinate axes.
Fig8.
As another application of Steiner problem, let us point out Evolution Theory (Phylogeny). It is well-known that Evolution Theory describes the origin of species process as a tree.
In Darwin’s time such trees were constructed on the base of exterior or/and functional properties. After beginning and development of modern genetics and proteomics, a new approach to Evolution Theory appeared. Due to this approach, each species is the corresponding genotype, and the constructing of evolutionary trees need to be based on the reasons of the minimal number of mutations necessary for Evolution. So, we have the following problem. We are given with a set of species-genes (or the corresponding proteins), each of which is a very long word over a given alphabet (in the case of genes this alphabet consists of 4 letters corresponding to the nucleic acids forming DNA). Besides, we are given with a distance function on the pairs of words, which corresponds to the minimal number of changes-mutations necessary to transform one word to the other one. We need to find a tree, connecting the given boundary set of species and having the least possible length in the sense of this distance. So, we have a generalized Steiner problem on the space of words.
The main works in this branch of mathematics are devoted to the studying of the shortest networks, i.e. Steiner minimal trees. We consider a more general class of networks, namely, the networks which are the shortest “in small” (each sufficiently small part of such a network is a Steiner minimal tree with the corresponding boundary). Such networks are called local minimal networks.
The local structure of local minimal networks in the plane is the same as the local structure of Steiner minimal trees. Namely, these networks consist of straight segments joining aby the angles of at least 120 degrees. In particular, the degree of each vertex of such a network is at most three (at most three segments can join at a vertex).
We are especially interested in local minimal binary trees, i.e. local minimal trees without cycles and without vertices of degree two. The reason is that each local minimal tree can be represented as the union of local minimal binary trees joining with each other at the vertices of degree 2 (in the initial tree) by the angles of at least 120 degrees. Notice that a Steiner minimal tree is a particular case of a local minimal network.
The interest to local minimal trees goes back to the famous Melzak algorithm (1960) constructing Steiner minimal trees. The idea of the algorithm s simple – to look over all possible local minimal trees (which are the unions of local minimal binary trees), and than to choose the shortest one. Thus, first of all, it is necessary to know how to construct a local minimal binary tree of a given combinatorial structure (topology), spanning a given boundary set. The idea of this construction goes back to Simpson’s method of the Torricelli point finding, see above. To avoid cumbersome descriptions we consider an example.
Thus, let us construct the local minimal network spanning the vertex set M of the square ABCD and having the structure shown in Figure.
Fig9 Demonstrates us the square ABCD and the topology of a binary tree.
Melzak algorithm consists of two stages, so called forward and reverse stages. During the forward stage we consecutively reconstruct the boundary set and the topology of the binary tree decreasing the number of boundary points.
Namely, let us choose the pairs of boundary vertices which are adjacent to the edges incident to a common vertex of degree three. Such pairs of edges are called moustaches. In our case the pairs A, B and C, D of vetices correspond o moustaches. (It is easy to see that any binary tree with more than three vertices of degree one has at least two moustaches.) Let us fix one of such pairs, say the pair A, B. On this pair we construct the equilateral triangle ABX, see next Figure.
Fig10 Shows us the reconstructed boundary set X,C,D and the reconstructed topology of a binary tree.
Reconstruct the set M as follows: we throw out the points A and B, and add the point X just constructed. Thus, now the reconstructed boundary set consists of three points X, C, and D. Now we reconstruct the topology of the binary tree. To do this, we throw out the edges-moustaches, and assign the new vertex of degree 1 just obtained to the boundary vertex X. That finishes the first step of the forward stage of Melzak algorithm.
During the next step of the direct stage, we choose some pair of boundary points corresponding to some moustaches again, and repeat the procedure. Namely, choosing, for example, the pair C, D, we again construct the equilateral triangle CDY. Then we again reconstruct the boundary set by throwing out the chosen vertices C and D corresponding to the moustaches and by adding the new vertex Y. And then we again reconstruct the topology by throwing out the edges-moustaches and by assigning the new vertex of degree 1 to the new vertex Y. The direct stage of the algorithm stops, when the resulting boundary set consists of two elements, and the resulting topology is the topology of the simplest tree consisting of the unique edge, see Figure.
Fig11 Illustrates us that the forward stage of Melzak algorithm stops.
Now let us describe the reverse stage of Melzak algorithm. During this stage we need to reconstruct the local minimal binary tree we looked for, if possible. First of all, let us join the two points constructed by the straight segment (in our example it is the straight segment XY). Then we consecutively reconstruct the tree. We start with the vertex that was added last (in our case it is the vertex Y), and remember that two vertices of the “previous” boundary set that generated this vertex (in our case they are the vertices C and D). Due to our construction, the points C, D, and Y are the vertices of a regular triangle. Circumscribe a circle around this triangle. The intersection point of this circle and the segment XY is the additional vertex of the local minimal tree with the boundary X, C,D we looked for (providing all the angles at the vertex are equal to 120 degrees).
Fig12 Demonstrates us reconstruction of the local minimal binary tree with the boundary X,C,D and additional vertex T1.
During the next step of the reverse stage of Melzak algorithm we take the next added vertex (in our example it is the vertex X), reconstruct the vertices of the “previous” boundary set which generated this vertex (in our case they are the vertices A and B), construct the equilateral triangle again and circumscribe the circle around it. The intersection point of the circle and the edge of current minimal tree coming to the vertex under consideration (in our case – the vertex X) is the next additional vertex of the local minimal binary tree with the new boundary (in our case with the boundary A, B, C, D). Algorithm stops either if the reconstruction of the local minimal tree is impossible, or if the tree we are looking for is reconstructed.
Fig13 Shows us that Melzak algorithm stops.
Notice that during the forward stage of Melzak algorithm, each time we have two ways to construct the regular triangle. Formally, we have to consider all possible cases consequently. For each next possibility we have to apply the reverse stage of the algorithm until we either reconstruct the desired tree, or we verify all the possibilities and find out that the tree can not be reconstructed in any case. In 80th Hwang thought out a modification of Melzak algorithm, which gives an opportunity to choose the location of the next equilateral triangle from the geometry of the boundary set. This idea of Hwang permited to create so called Melzak-Hwang algorithm that verifies the existence of a local minimal binary tree of a given topology on a given boundary set in linear time.
Unfortunately, the enumeration concerned with the great number of possible combinatorial structures (topologies) of binary trees still is not overcome. Moreover, it is well-known that the Steiner problem is NP-hard (i.e., informally speaking, “most likely” there is no a polynomial algorithm solving this problem). This reasoning makes the problem of finding some geometrical characteristics of the boundary set M and of the ambient space W such that give restrictions on possible structure of local minimal trees spanning the set M in the space W even more actual.
One of such properties is the presence of a rich symmetry group of the boundary set. In particular, it is interesting to describe all local minimal trees spanning the vertex sets of regular polygons. It is not difficult to describe Steiner minimal trees with such boundaries. Namely, in the cases of equilateral triangle, square and regular pentagon the corresponding Steiner minimal trees can be found easily by Melzak algorithm, see Figure.
Fig14.
The remaining cases are described in the next theorem.
Theorem (Jarnik, Kossler, Du, Hwang). For n ≥ 6, Steiner minimal tree spanning the vertices of the regular n-gon consists of its (n-1) sides.
The description of local minimal networks, spanning regular boundaries (i.e. the vertex sets of regular polygons) is not known yet. The authors obtained a complete classification of a special class of local minimal binary trees with regular boundary – so called skeletons. It turns out, that there exist two infinite and one finite (with respect to n) series of such networks. Here we give the corresponding illustrations. First Figure shows local minimal binary trees of type “snake” which exist for an arbitrary regular n-gon starting from n=3. The next infinite series is formed by so-called “T-joints”, which exist not for an arbitrary n, but only for n=6k+3, k ≥ 1. At last, the unique finite series of local minimal binary trees-skeletons consists of four networks appearing at regular n-gons for n=24, 30, 36, and 42, see below Figure with n=24. Notice that the proof of this result is highly non-trivial, see Ivanov, Tuzhilin.
Fig15.
Fig16.
Fig17 Shows us “Sixlegs” network for n=24.
Another important particular case of boundary sets is the boundaries lying in the standard circle. The following generalization of Jarnik-Kossler-Du-Hwang theorem holds.
Theorem (Du, Hwang). If M is a finite subset of the circle of radius r, and the polygon M has at most one side longer than r, then Steiner minimal tree spanning M consists of all the sides if the polygon except the longest one. In particular, a binary Steiner minimal tree spanning M does not exists.
It is easy to see, that if a subset M of the circle lies in a sufficiently small neighborhood, then there is no even a local minimal binary tree spanning M. However, what can we say about “uniform” subsets of the circle? More exactly, is it possible to construct an example of subsets family {Xn} of the circle, such that the subsets Xn tend to fill the whole circle as n tends to infinity, and each subset Xn can not be spanned by a local minimal binary tree (as we have seen, regular polygons match the first but not the second condition)?
Let us look for an example in the class of so called quasiregular polygons. A polygon M is said to be quasiregular if its vertices lie on the circle in such a way that they can be separated by vertices of some regular polygon inscribed in this circle, see Figure.
Fig18.
We consider quasiregular polygons of special kind, which are called ε-quasiregular. Let us gve the corresponding definition. Let P1, …, Pn be the vertices of a regular polygon. Let us fix a number ε, 0< ε < π/n. Let us fix a set s = (s1, …, sn), where each si is either +1, or –1. Now we rotate each point Pi by the angle si ε , and let Mi be the point obtained from Pi. The quasiregular polygon { Mi } constructed in such a way is called ε-quasiregular polygon of type s. In Figure we have n=8, ε = π/16, s = (1,1,1,-1,1,1,1,-1).
The following result holds.
Theorem (Ivanov, Tuzhilin). Let s be a periodical sequence of the length 10k with period (-1,1,1,1,-1,-1,1,-1,1,-1), and ε be a positive number such that π/2n < ε < π/n. Then for k ≥ 7 the vertex set of an ε-quasiregular n-gon of the type s can not be spanned by any local minimal binary tree.
In Figure a 70-gon meeting the conditions of Theorem is depicted.
Fig19.
The complete proof can be found in Ivanov, Tuzhilin. Here we give only a short sketch of the proof. Let us underline, that the statement and the proof of Theorem were found in computer experiments.
The proof is based on the concept of “germ of snake” emitted from a vertex of a convex polygon. Informally speaking, we construct a local minimal binary tree of snake-type starting from a marked vertex of the polygon, and span step by step the consecutive vertices by consecutive appendices of the snake, see Figure.
Fig20 Demonstrates us vertex, appendices.
The length of the germ is the number of its appendices. It turns out that each local minimal binary tree spanning the vertices of a quasiregular polygon contains a sufficiently long germ of snake. More exactly, for n ≥ 18, each local mnimal binary tree spanning a quasiregular n-gon contains a germ of snake whose length is at least 2 [(n-6)/12], where [x] is the greatest integer which is less than or equal to x. The following question arises.
Let us fix a positive k. Can one find n > k, 0 < ε < 2π/n, and an ε-quasiregular n-gon M, such that a germ of snake of the length k can not be emitted from any vertex of M?
To solve this problem we make the following computer experiment. We simulate all ε-quasiregular polygons as follows. Let V be the set of all the words consisting of k letters “+1” and “–1”. Let us consider the oriented graph G with the vertex set V, whose edge vw goes from the vertex v to the vertex w if and only if the (k-1)-suffix of the word v (i.e. its suffics consisting of (k-1) letters) coincides with the (k-1)-prefix of the word w. For example, an oriented edge goes from the vertex v = (-1,1,1,1,-1,1,-1) to the vertex w =(1,1,1,-1,1,-1,1) (for simplicity we identify the words and the vector-rows).
Assertion. Under the above notations, ε-quasiregular polygons are all possible closed route in the graph G.
In Figure the graph G for k=2 is depicted.
Fig21.
Starting from the red vertex and routing along the red edges in such a manner that we pass each edge two times, we construct the ε-quasiregular 6-gon of the type s = (-1,1,-1,-1, 1,-1).
Further, for each sequence s from V, we verify if it possible (for some ε) to emit a germ of snake spanning the vertices corresponding to s (that condition is equivalent to solvability of some linear inequalities on α = 2π/n and ε). In Figure we give an example for s=(1,-1,1,1,-1).
Fig22 Illustrates us that the beginning vertex of the germ of snake should be here.
By T we denote the set of all s, such that the germ of snake can not be emitted. Let H be the subgraph of G generated by T (i.e. we take all the edges of G that join some vertices from T).
Assertion. Each cycle of the graph H corresponds to a quasiregular polygon whose vertex set can not be spanned by any local minimal binary tree.
Construction of the graph H and finding cycles in this graph was realized with the help of computer. We use well-known software package Mathematica®. It turns out that for k < 10 the corresponding graph H does not contain cycles. For k=10 the graph H contains 488 vertices, and has the following form.
Fig23 This Figure is obtained by Matematika® also.
Using Matematika® we find out that this graph contains exactly two cycles of length 10. One of these cycles is shown in red in next Figure.
Fig24.
This cycle generates the series of examples of quasiregular polygons described in Theorem.