In the present paper we consider one-dimensional branching extremals of Lagrangian type functionals. Such extremals appeared first as solutions of the classical Steiner problem asking to find the shortest network, i.e., a connected system of paths of the least length, among all networks spanning a given finite set of terminal points in the plane. The Steiner Problem has a long history and attracts the attention of many well-known mathematicians as from P. Fermat and C. Gauss. Among the reasons of this unabating interest is a lot of important applications of the Steiner problem such as Transportation problem.
In the case of the Steiner problem the corresponding Lagrangian is the length of the velocity vector of an edge of a network in consideration and the obtained functional is called the length functional. It is well known that a network is an extremal of the length functional if and only if it is local minimal, i.e., each sufficiently small part of such a network is a solution of the Steiner Problem with respect to the appropriate terminal set. However, this fact have no place for general functionals. In the present paper we investigate the functional of Manhattan length whose lagrangian equals the sum of absolute values of projections of velociy vector onto coordinate axis. Such functionals are useful for solving problems appearing in Electronics, Robotics, chip design, etc. It turns out that for such functional the local minimality does not imply the extremality (however, each extreme network is local minimal). In the case of Manhattan plane we present a ctriterion of extremality of a local minimal network. This criterion demonstrates that the extremality with respect to Manhattan length functional is a global topological property of networks.
Key words: Branching extremals, branching geodesics, networks, Steiner Problem, Rectilinear Steiner Problem, local minimality, extremality, functional, lagrangian.
Traditionally the shortest networks are investigated. In the present work we investigate wider classes of networks: locally shortest (so-called local minimal ) networks, and critical networks, i.e., critical points of the Manhattan length functional, see exact definitions below. Notice that in the case of Riemannian length functional, local minimal networks are critical points of the length functional, and, if splitting of vertices is permitted, then the reverse statement is also true, see [67]. In other words, the class of local minimal networks and the class of critical networks coincide for the case of Riemannian length functional. It turns out, that in the case of Manhattan length functional the class of local minimal networks is wider than the one of critical networks. The main aim of the present work is the description of the difference between these classes.
The first works on the shortest networks in the sense of Manhattan length appeared at 60th, see [34], due to the intensive development of Electronics and Robotics. The interest to the Manhattan length appeared due to the fact that, as a rule, conductors on printed circuits have a form of polygonal lines formed by horizontal and vertical segments, and therefore the Manhattan length of the conductors coincides with their Euclidean length. Similar situation takes place in Robotics. Rather the first systematical investigation of the shortest networks in the sense of Manhattan length (so-called shortest rectilinear trees ) was made by Hanan [42] in 1966, who described some important general properties of such networks. In particular, Hanan showed that among the shortest rectilinear trees there always exists one which is a subset of the union of all vertical and horizontal straight lines passing through the boundary points (the union is called Hanan lattice ). Notice that the edges of the shortest rectilinear tree can be chosen in many different ways without changing the length of the tree. But, starting from the work of Hanan [42] the edges of the shortest trees are traditionally chosen in the form of polygonal lines whose links are parallel to the Cartesian coordinate axis.
After 10 years Hwang [47] described the possible structures of the shortest rectilinear trees under the assumption that the given boundary set can be spanned by at least one nondegenerate shortest tree G0. The latter means that the degrees of all the boundary vertices in G0 equal to 1. In particular, the tree G0 has no vertices of degree 2. Hwang proved that in this case the shortest tree has one of the following two possible structures, which are depicted in Figure 1.
However, an efficient algorithm constructing a shortest rectilinear tree had not been found yet. The reason was explained in 1977 by Garey and Johnson [35], who proved that the problem of finding the shortest rectilinear tree is NP-hard, i.e., a polynomial algorithm solving the problem does not exist most likely. The fact makes the investigation of the restrictions to the structure of the shortest networks even more actual.
The idea to consider local minimal networks appeared first during the investigation of the shortest networks in the case of Euclidean length. Namely, after describing of the local structure of the shortest networks (to do this it suffices to solve the problem with at most one additional vertex) it is natural to try to describe all the networks satisfying the conditions obtained. These networks form a wider class and usually are referred as local minimal networks. Notice that the first real-life algorithms constructing the shortest Euclidean trees (they were based on the Melzak algorithm [76]) enumerated all possible local minimal trees and selected the shortest one among them.
In real situations, sometimes it is essentially easier to find the shortest tree than to enumerate all local minimal networks. For example, if the boundary set is the vertex set of a regular n-gon, n ³ 6, then the shortest network is the n-gon itself without one of its sides (this result was obtained by Jarnik and Kössler [68] for n ³ 13, and by Du, Hwang, and Weng [26] for 6 £ n £ 12). But the set of local minimal networks in that case is rather more complicated, see [60]. In the case of the shortest Manhattan networks with so called rectilinear-convex boundaries, a polynomial algorithm constructing such networks is known, see for example the work of Richards and Salowe [84].
Notice that the works listed above investigate some algorithmic aspects of the problem mainly. In particular, the difference between local minimal networks (i.e., in the context, the networks having the same local structure as the shortest networks have) and critical networks has not been observed. The geometry and topology of local minimal and critical networks have also not been investigated.
Our approach gives an opportunity to consider the problems of that type as natural generalizations of classical (one-dimensional) variational problem to the case of branching extremals1. The approach is based on a synthesis of ideas of differential geometry and convex geometry on the one hand, and the ideas of discrete geometry and combinatorics on the other hand. In the case of Euclidean length, where the extremal can be considered as branching geodesics, we mention, beside the works of the authors, the works of A. Vdovina, I. Iskhakov, G. Karpunin, G. Lawlor, V. Manturov, F. Morgan, T. Pavlyukevich (Anikeeva), M. Pronin, I. Ptitsyna (Shklyanko), E. Selivanova, J. Hass, and others, who consider minimal networks from the same point of view, see a review in [67]. Critical networks with respect to some other functionals of ``elliptic type'' were investigated by G. Lawlor and F. Morgan [74], [75].
From the geometrical point of view, interests to the networks extremal with respect to Euclidean and Manhattan length can be explained by the fact that these two functionals are, in some sense, the limiting cases of the functionals generated by Banach-Minkowski metrics. Namely, the Euclidean length is generated by the most symmetrical and strictly convex norm, and the Manhattan length is generated by the non-strictly convex norm with the maximal possible length of the circle. Just the failure of the strict convexity property leads to the fact that in the case of Manhattan length the classes of local minimal and critical networks are different, unlike the Euclidean case. Similar effects apparently take place also for the other Banach-Minkowski norms, see [53].
The debate on the necessity to investigate not only absolute minima but other critical points has a long history2. Notice that the critical points different from absolute minimum or maximum appear naturally in multidimensional variational calculus too. A classical example is given by theory of minimal surfaces (minimal surface is a mathematical model of soap film or, more general, of an interface surface between two physical mediums in equilibrium). It is well-known that, generally speaking, the same one-dimensional contour can be spanned by several soap films having not only different geometrical form, but also having different topological structure, see, for example [17], [31], [32], [92], [44]. These films can correspond not only to absolute minima, but also to local minima and saddle points of the Area functional. Notice that the latter ones are non stable (see, for example [17], where the experiments of Poisson observing nonstable soap films are described). The questions of stability, i.e., the questions of finding out if a given surface is a local minimum or a saddle point are explored intensively in minimal surfaces theory, in particular, by the authors, see [51], [45]-[46], [91].
On the other hand, the conversion to the investigation of all critical points leads to a new view of the nature of absolute minima and maxima, makes their global properties more clear. Just that idea works in Morse Theory.
In the present work the following results are obtained. Theorem 2.3 gives a criterion of that a local minimal network in the sense of Manhattan length is a critical network with respect to the Manhattan length functional. The main difficulty here consists of the necessity to control global deformations of local minimal networks attending all possible bifurcations of the vertices.
The authors are glad to use the opportunity to express their deep gratitude to Jürgen Jost for the interest demonstrated to our work and for the possibility to work jointly and fruitfully in MPI fur Mathematik in den Naturwissenschaften, Leipzig. The authors are grateful to Anatoly Fomenko for his permanent attention to our work. The authors are very thankful to Professor Frank Morgan for his comments which have improved the main results of the present paper.
A homeomorphism of graphs taking vertices into vertices is called a (topological) equivalence. Graphs G1 and G2 are called equivalent if there exists an equivalence j G1® G2. In the sense of Graph Theory equivalent graphs are organized in the same way and they are not distinguished. In what follows all terminology from Graph Theory and Topological Spaces Theory will be applied to topological graphs without additional comments.
Let H be a subgraph in a topological graph G. The factor space G/H can be endowed evidently with the unique natural structure of a topological graph. The graph G/H is called the factor graph of the graph G over the subgraph H. A mapping j from a graph G1 to a graph G2 is called a projection, if it coincides with the standard projection p G1® G1/H = G2 for some subgraph H Ì G1. Note that the projection is continuous and closed by definition.
Suppose that a subset B of the vertices set of a graph G is marked. Such graph G is called a graph with the boundary ¶G = B. The vertices from ¶G are called boundary vertices or fixed vertices, and all the other vertices are called interior ones or movable ones. The edges of the graph incident to its boundary vertices are called boundary edges, and an edge which is not incident to any boundary vertex is called an interior one.
Let G be a graph with some boundary B. Let 
B denote the
subgraph in G generated by all movable vertices of the graph G. The
subgraph B is called the movable subgraph of the graph G
(with respect to the boundary B). Note that the movable subgraph
consists exactly of all movable edges of the graph G.
We defined above the equivalence of graphs. In the case of graphs with boundaries we always shall suppose that any equivalence generates a one-to-one mapping between the boundaries of such graphs. Also, if G is a graph with a boundary ¶G, then the boundary of a factor-graph obtained from G is defined as the image of ¶G under canonical projection.
Let G be an arbitrary graph with a boundary ¶G (the boundary can be empty) and P Î G be some of its points. An admissible neighbourhood U Ì G of a point P in the graph G is a closure of a connected neighbourhood of this point which does not contain any vertices of the graph G different from P, if P is a vertex, and which does not contain loops from G. Let us endow the neighbourhood U with a structure of graph by calling the vertices all the points from ¶UÈ{P} and by calling the edges the interiors of the segments from U joining these points. The obtained star we denote by GU and call the local graph centered at P. Define the canonical boundary ¶GU of a local graph GU by putting into it all the vertices from ¶U and also the vertex P if P is a boundary vertex of the graph G. In other words, ¶GU = (¶GÇU)È(GǶU).
Note that the number of edges of an arbitrary local graph G centered at a vertex v of the graph G equals the degree of this vertex in the graph G.
Let G be a graph with boundary ¶G. Cut the graph G over all its boundary vertices of degree more than 1 and denote the obtained connected components by Gi. For each component Gi we define the boundary ¶Gi as the set of all the vertices from Gi of degree 1 which obtained from the boundary vertices of the initial graph G. Each component Gi with the boundary ¶Gi is called an nondegenerate component of the graph G.
Further, if M Ì X is the image of a boundary mapping ¶G, then we say that the parametric network G spans the set M (by the mapping ¶G).
Let G :G® X be an arbitrary parametric network and I = [a,b] be a segment.
of any edge e of the
graph G the restriction of the mapping Y onto ×I is
either smooth or piecewise smooth. The family of velocity vectors of the
curves Gt(g) at t = 0 over all point g Î G is called the
deformation field of Gt.
A network-trace U is said to span a subset M Ì X if M is the image of the boundary mapping of some and, thus, of any parametric network from U.
A canonical representative of a trace 
is a parametric network
G Î such that any parametric network G¢ from can be projected
onto G. It is not difficult to show that up to topological equivalence
any trace has a unique canonical representative, see [66].
A local trace or a a local network of a trace-network
is any
trace of the form [Gl], where Gl is an arbitrary local network of
a canonical representative G of the trace .
(Local) deformation of a trace is any one-parametric family of
networkst = [Gt], where Gt is a deformation of some parametric
network G from .
The notation for traces we won't use below.
In what follows we shall work mainly with networks in the plane. A finite
collection of curves immersed into the plane is called an immersed
planar graph. If all these immersions are embeddings and the images of
any two such embeddings do not intersect each other, then the immersed
planar graph is called simply planar graph.
Let G be an arbitrary planar tree. Using G we construct an immersed planar graph KG coinciding with its unique cycle as follows. A path g in G joining two vertices of degree 1 and such that all the edges from G not belonging to g but incident to the vertices of g lie from one side of g is called a Steiner path. Consider all Steiner paths in G. We distinguish the edges and the vertices of different Steiner paths also if they coincide in G. Now, glue all these Steiner paths by their common (in G) beginning and ending vertices. It is easy to see that we obtain an immersed planar graph coinciding with its unique cycle. This graph is called the contour of the planar tree G and is denoted by KG.
Let X be a finite dimensional linear space with some norm ||·|| and g [a,b]® X be a continuous curve. The curve g is called measurable if there exists a limit l(g) of lengths of the polygonal lines inscribed into the curve. Such number l(g) is called the length of the curve g. Notice that if the curve g is piecewise smooth, then it is measurable and
|
Let G be an arbitrary piecewise smooth network in X. Then the length l(G) of the network G is the sum of the lengths of its edges. A network G spanning a set M Ì X is called the shortest network if its length does not exceed the length of any other piecewise smooth network spanning M.
[Definition.] A network G is called critical or extreme if for any deformation Gt, t Î [0,1], where Gt = 0 = G, the following condition holds
|
Suppose that some Cartesian coordinates (x1,¼,xn) are fixed in \Bbb Rn. Recall that the Manhattan norm of a vector y = (y1,¼,yn) is the following number:
|
Assertion 1 Let A and B be arbitrary points of a linear space X with a norm. Then any straight segment [A,B] is the shortest curve joining these points.
|
This estimation is exact. Namely, for any integer k ³ 1 there exists a planar linear tree G such that twG = 12(k-1)+6 and x(¶gG) = k.
To start with, we describe critical and local minimal curves.
Assertion 1
A curve g joining a fixed pair of points is critical if and only if it
is monotonic. Moreover, any critical curve is a shortest one.
A curve g joining a fixed pair of points is local minimal if and only if
there exists a finite open covering of its parametric segment such that
the restriction of the curve g onto the closure of any of these
covering elements is a monotonic curve.
Now, let us describe local minimal networks.
Let G be a network in Manhattan space all of whose edges are local minimal curves and let V be an arbitrary its vertex. By the monotonic neighbourhood of the vertex V we call the local network consisting of monotonic segments of the edges incident to V such that each of these segments contains V and is the maximal segment with such properties. A monotonic neighbourhood of the vertex V with V removed is called the punctured monotonic neighbourhood of V.
Theorem 1
A network G with a boundary is local minimal in Manhattan space if and
only if the following conditions hold.
The following result holds.
Theorem 2 Any critical network in Manhattan space is local minimal. In particular, the local structure of critical networks is described by Theorem 2.1.
Now, let us describe some properties of critical networks in Manhattan space Rn which immediately follow from Assertion 2.1. Let G be an arbitrary network. A maximal path in G (it can be cyclic) all of whose interior vertices have degree 2 in G and which are not boundary vertices of G is called a thread. Notice that any edge of G is a thread by definition.
Corollary 2 Any thread of a critical network on Manhattan space is a monotonic curve.
by changing the threads of G with straight
segments joining the same vertices. The network is called the
linearization of the network G.
The following important result is evident.
Assertion 2 A network G is a critical one in Manhattan space \Bbb Rn if and only if all its threads are monotonic and its linearization is a critical network.
Corollary 3 Any immersed critical network in Manhattan space \Bbb Rn can be obtained from some critical linear network without movable vertices of degree 2 by replacing of edges of the latter one with monotonic threads joining the same points.
Thus, it suffices to describe only linear critical networks without movable vertices of degree 2.
Let g be a horizontal fragment. A nonhorizontal edge e incident to a vertex v from g is called onesided if it is the unique nonhorizontal edge incident to v. A onesided edge incident to an interior vertex v of a fragment g is called static if v is a boundary vertex of the tree G. A onesided edge incident to an ending vertex of a fragment g is also called static. All remained onesided edges we call floating.
Further, a vertex v of a fragment g such that v is not incident to a onesided edge is called static if in the tree G it is a boundary vertex of degree 1 or 2. Note that a vertex of g is static if and only if it is not incident to any nonhorizontal edge of the network G and belongs to the boundary of G.
Partition the set of all nonhorizontal edges incident to a fragment g into two classes C1 and C2 depending on which half-plane bounded by a straight line passing through g these edges lie in. By tis and tin we denote the numbers of static and floating edges in the class Ci, i = 1,2. The number indi = 2tin+tis is called the index of the class Ci and the number ind(g) = |ind1-ind2| is called the index of the fragment g. To be definite, we assume that the class C1 consists of edges placed in upper half-plane with respect to g.
Further, by es we denote the total number of onesided edges, i.e., es = t1s+t2s and by vs the total number of static vertices of the fragment g. The number stat(g) = 2vs+es is called the static degree of the fragment g.
The corresponding notions for a vertical fragment can be defined similarly.
Theorem 3
A network G in Manhattan plane R2 is critical if and only if all
its threads are monotonic curves, the linearization Gl of G is
local minimal, and the index of any fragment g of Gl does not
exceed the static degree of this fragment :
ind(g) £ stat(g).
[Proof.] By Assertion 2.2, we can assume that the network G is linear local minimal one without movable vertices of degree 2. In particular, the network G coincides with its linearization Gl. Besides that, it is sufficient to consider only those deformations of the network G which preserves the edges monotonicity. This implies that it suffices to consider only deformations in the class of linear networks. To calculate the first variation of a straight segment length with respect to Manhattan norm the following function will be useful
|
F(x,y)= |
|
y for x>0 |
|
-y for x<0 |
||
|
|y| for x=0 |
Define three vector-valued functions on Rn as follows
where X = (X1,¼,Xn). Note that a component of the vector null(X) equals zero if and only if the corresponding component of the vector X does not vanish. In the opposite case this component of the vector null(X) equals 1. Notice also that the functions null(X) and mod(X) are even, but the function sign(X) is odd.
In what follows it will be more convenient to consider the functions null(X) and mod(X) as the ones defined on nonordered pairs of vectors, namely
|
Lemma 1 [The first variation of segment length]
Let [A,B] be an arbitrary segment in Manhattan space Rn
thissegment can be degenerated .
Consider some its linear deformation such
that the point A = (A1,¼,An) moves along the curve
A(t) = A + t x + o(t) and the point B = (B1,¼,Bn) moves along the
curve B(t) = B + t h + o(t), where t Î [0,1], and o(t) stands for an
infinitesimal of order t, t® 0. Then the function l(t) of the
Manhattan length of [A(t),B(t)] is differentiable at t = 0 and
d
dt
ê
ê
t = 0
l(t) =
å
i
f(Bi-Ai,hi-xi),
d
dt
ê
ê
t = 0
l(t) = sign(A-B),x + sign(B-A),h + null({A,B}),mod({x,h}) .
Lemma 2.1 gives us an opportunity to write down the following formula of the first variation for a linear network.
Lemma 2 [The first variation of network length]
Let G be a linear network in Rn and Gt = [Ft], t Î [0,1],
be its local deformation in the class of linear networks, where Ft
is the corresponding deformation of some parametric network
F = F0. By x we denote the deformation field of Ft. Let
V be an arbitrary movable vertex of the network F. By SV we
denote the sum of vectors \operatornamesign(V-V¢) over all nondegenerate edges VV¢
of the network F. Then
Return to the proof of Theorem 2.3. Suppose first that G is a critical network and g is its arbitrary fragment. Consider a linear deformation Gt of the network G which moves the fragment g in a direction perpendicular to g in such a way that g remains parallel to its initial position and each vertex which moves under the deformation Gt does that with unit speed. To be definite, we assume that g is a horizontal fragment which moves upward. In the neighbourhoods of vertices we define the deformation Gt as shown in Figures 3 and 4.
 |
|
| Figure 3: Splitting the vertices under deformation Gt. White vertices are nonboundary ones; black vertices are boundary ones; ``-'', ``+'', or ``0'' means negative, positive, or zero contribution in that case. | |
 |
|
| Figure 4: Splitting the vertices under deformation G t. White vertices are nonboundary ones; black vertices are boundary ones; ``-'', ``+'', or ``0'' means negative, positive, or zero contribution in that case. | |
As above, partition nonhorizontal edges into two classes Ci by putting into the class C1 the edges from upper half-plane. Recall that by tis and tin we have denoted the numbers of static and, respectively, floating onesided edges from the ith class, by vs the total number of static vertices in g, and by es the sum t1s+t2s. The first variation formula, see Lemma 2.2, and the fact that the network G is critical imply
|
|
|
|
Note that our calculations leads to the following result.
Lemma 3
The inequality ind(g ) £ stat(g ) is equivalent to the
following system of inequalities:
tn1 £
tn2+vs+ts2
tn2 £
tn1+vs+ts1.
Now, prove the converse statement of the theorem. Let G be a local minimal network without movable vertices of degree 2 such that for any its fragment g¢ the inequality ind(g¢) £ stat(g¢) holds. Consider an arbitrary deformation Gt = [Ft] of the network-trace G through the class of linear networks remaining fixed the boundary of the network. This means that we fix a parameterization F = F0 of the trace G (recall that such a parameterization can contain some degenerate edges). Show that the first variation of this deformation is nonnegative.
Without loss of generality we assume that the deformation Gt possesses the following properties.
We transfer all terminology introduced above to the parametric network F. Let p F®G be a projection of the parametric network F onto the canonical representative G. An edge of F such that its image under the projection p is a horizontal (vertical, free) edge is called horizontal (respectively, vertical, free). Notice that horizontal, vertical and free edges of the network F are all its nondegenerate edges.
Let g¢ be an arbitrary fragment of the network G. The fragment g of the parametric network F corresponding to the fragment g¢ is the preimage of the path g¢ under the projection p. A section of the network F is any its fragment corresponding to a section.
Let g be a fragment of the network F corresponding to a fragment g¢. The extension T(g) of the fragment g is a subnetwork in F obtained from g by adding all the edges of F incident to it. Notice that all added edges are nondegenerate. Recall that the nonhorizontal edges of the network G corresponding to the edges added are partitioned into the classes C1 and C2. This partition induces a partition of the corresponding edges of the network F into two classes which will be denoted by C1 and C2 as well.
Write down the first variation formula for the deformation Ft. Lemma 2.2 implies that the obtained expression can be represented as the sum of two expressions åv and åh such that the first one depends only on vertical components of the deformation field, but the second one depends only on horizontal components. We shall show that each of these terms is nonnegative.
Consider the expression åv. Lemma 2.2 shows that this expression consists of two parts: linear åvl and nonlinear åvn. And also, the part åvn is a sum of absolute values, thus, it is nonnegative. We shall show that the linear part åvl can be compensated by the nonlinear one åvn.
Lemma 4 Nonzero contribution into åvl is given only by deformation vectors of those vertices of the network F which lie in horizontal sections.
Let g be a horizontal section of the network F and T(g) be its extension. By definition of a section, all horizontal edges of the tree T(g) belong to g. Besides, all degenerated edges from T(g) lie, evidently, in the preimage of the vertex set of the corresponding section g¢ of the network G. Therefore, the extensions of any two different horizontal sections of the network F intersect each other neither by horizontal, nor by degenerate edges. On the other hand, Lemma 2.2 implies that the value åvn equals to the sum of terms over all horizontal and degenerate edges, and each of these terms depends only on the value of the deformation field on the boundary of the corresponding edge. Thus, åvn is more or equal the sum of terms åvn(g) over all horizontal sections, where åvn(g) denotes the contribution of the edges from T(g) into nonlinear part. Our aim is to prove that
|
Prove the inequality (*). Notice first that, by definition, the expression åv(g) depends only on vertical components of the vectors of the deformation field. Thus, to prove the inequality (*) we may assume that the deformation field is vertical.
For what follows we need to correct the network G and the deformation Ft preserving the inequalities from the condition of the theorem and the both linear and nonlinear parts åvl and åvn (the same can be done for horizontal components).
Lemma 5
Under the above assumptions on the deformation Ft, suppose that one
of the following possibilities takes place.
Reconstruct the networks F and G by adding the point V and,
respectively, the point p(V) to the boundary sets of these networks.
The obtained networks we denote by [`(F)] and [`(G)]. Then the
network [`(F)] can be projected onto the network [`(G)], the network
[`(G)] is a canonical representative of the corresponding trace, and
[`(G)] satisfies the conditions of the theorem. The deformation Ft
generates a deformation [`(F)]t of the parametric network [`(F)]
and defines a local deformation of the trace [`(G)]. The linear and
nonlinear parts of the vertical and horizontal components of the first
variation formulas for the deformations Ft and [`(F)]t
coincide.
Lemma 2.5 gives an opportunity to assume without loss of generality that the deformation Ft remains fixed only the boundary vertices of the network F and all nonzero deformation vectors are codirected with Y-axis, i.e., they directed upwards.
Let g¢ be a section of the network G. Cut g¢ over all its noninterior vertices incident to those edges from C1 which are not floating. The closures of the obtained components we denote by g¢i.
Consider an arbitrary component g¢i. Partition the vertices from g¢i onto two classes U1 and U2 by putting into the first one all the vertices incident to the edges from C1. Orient g¢i in one of two possible ways that gives an order on the set of vertices from g¢i.
Lemma 6 The class U1 can not contain more than two consecutive vertices.
|
|
|
Lemma 7 Between each two pairs H1 and H2 of adjacent vertices from U1 there is a pair of adjacent vertices from U2.
|
Lemma 8 Each nonending vertex x from the class U1 can be paired with a vertex from U2 adjacent with x in such a way that the obtained pairs do not intersect each other.
If the vertex x preceding to h belongs to U2 but it is not contained in a pair still , then we take the pair {x,h} as the next one and continue the procedure. Otherwise, by Lemmas 2.6 and 2.7, the vertex y consequent to h belongs to U2 and we take the pair {h,y} as the next one and continue the procedure.
Let us show that the described procedure is correct and we always come to an ending vertex of g¢i as a result. The fragment g¢i is partitioned by the pairs of adjacent vertices from U1 into several smaller fragments g¢ij. Each of these fragments is either bounded from the both its sides by pairs of adjacent vertices from U1, or some pair of this type is placed at one end of the fragment g¢ij and the other end of the fragment coincides with an ending vertex of g¢i.
Suppose first that g¢ij is bounded by two pairs H1 and H2 of adjacent vertices from U1. By Lemma 2.7, the fragment g¢ij contains a pair of adjacent vertices from U2 and all the vertices from U1 lying inside g¢ij are alternated with the vertices from U2. Thus, it is easy to see that our procedure starts from the first pair Hi, constructs the desired pairs for all the vertices from U1 lying inside g¢ij, and after that it comes to the last vertex from g¢ij. If the fragment g¢ij is bounded by exactly one pair H1 of adjacent vertices from U1, then, by definition, during the motion along g¢ij from this pair we meet a vertex from U2 after each nonending vertex from U1. Thus, our procedure starts with H1, constructs all desired pairs for all the vertices from U1 lying inside g¢ij, and after that comes to the ending vertex from g¢ij.
Now consider the remained possibility: suppose that the fragment g¢i has no adjacent vertices from U1. Then each vertex from U1 lying inside g¢i has an adjacent vertex from U2 at its both sides. Now the desired pairs can be constructed obviously. Lemma is proved. By U2(g¢) we denote the union of the sets U2 over all fragments g¢i. Lemma 2.8 implies the following result.
Lemma 9 Each floating vertex from the section g¢ can be paired with an adjacent vertex from U2 in such a way that the obtained pairs do not intersect each other.
Consider first an arbitrary pair {h,x} from Lemma 2.9, where h is a floating vertex and x is vertex from U2. By eh we denote the unique edge from C1 incident to h.
Using the pair {h,x} we construct a path Y in the network F as follows. There are two possibilities: either the vertex x is a boundary one of the network G, or it is movable vertex of degree 3 of this network. In the first case we define Y to be the unique path in the extension T(g) of the section g of the network F joining the unique boundary vertex X of the network F projecting into x with the unique nondegenerate edge Eh of the network F projecting into eh. In the second case, by ex we denote the unique edge from C2 incident to x and define Y as the unique path in the extension T(g) of the section g of the network F joining the edge Eh and the unique nondegenerate edge Ex of the network F projecting into ex.
Let E be a floating edge from C1 incident with the section g. Using E we construct a path Y in the network F as follows. By e we denote the image of projection into G of the edge E and let x be a vertex of the section g¢ of the network G incident to e. There are two possibilities: either the vertex x is a boundary one of the network G, or it is a movable vertex of this network. In the first case we define the path Y to be the unique path in the extension T(g) of the section g of the network F joining the edge E with the unique boundary vertex X of the network F projecting into x. In the second case, by ex we denote the unique edge from C2 incident to x and define Y as the unique path in the extension T(g) of the section g of the network F joining the edge E and the unique nondegenerate edge Ex of the network F projecting into ex.
By construction, the following Lemma holds.
Lemma 10 Let g be an arbitrary section of the network F. The paths Y constructed above for the section g do not intersect each other and contain all the vertices giving a negative contribution into åvl(g).
Let V1,¼,Vk be consecutive nonending vertices of the path Y enumerated from the unique edge E1 of Y belonging to C1. Notice that each vertex Vj is not a boundary one for the network F and all the edges joining the consecutive vertices Vj are degenerate. By xj we denote the projection of the deformation field vector at Vj onto Y-axis. There are two possibilities: either the ending edge E2 ¹ E1 of the path Y is degenerated, or not. In the latter case we have E2 Î C2 by construction.
In the first case the total contribution of the vectors xj into åv(g) has the form
|
|
Corollary 4
Let G be an embedded nondegenerate local minimal Manhattan network,
i.e., G coincides with its nondegenerate component. Then for any
fragment g the following conditions hold.
1 Problems of that type were stated first by French mathematicians, among them are Gergonne, Clapeyron and Lame. Gauss also interested with problems of this type. In his letter to Schumacher [37] he mentioned the problem of building a shortest railway system between the for German cities: Harburg (close to Hamburg), Bremen, Hanover, and Braunschweig. General problem of finding the shortest network spanning a given set of points of the plane was stated by Jarnik and Kössler [68] in 1934. Afterwards the problem became well-known as Steiner Problem, see the historical reviews in [10], [50], [58] or in [67].
Notice that the simplest case of Steiner problem when the boundary set consists of 3 points coincides with the following problem stated by Fermat: find the point in the plane such that the sum of the distances from that point to the vertices of a given triangle is the least. The principle difference between these two problems consists in the following: solving Steiner problem one does not know a priori neither the number of additional, i.e., non boundary vertices (these vertices are usually referred to as Steiner points ), nor the way how the vertices are joined. Underline that just that undeterminacy makes the Steiner problem NP-hard.
2 In 1746 Maupertuis published his famous Principle of Least Action: if there occurs some change in Nature, the amount of action necessary for this change must be as small as possible. Just after publication of the Principle, Maupertuis was criticized. On the one hand the question of priority was discussed, and on the other hand, it was understood fast that the Principle is not correct in such reading. For example, in 1749 and 1752 d'Arcy demonstrated how the Principle leads to false assertions using as a model the reflection of the light. D'Arcy showed that the ``thrift'' or ``wastage'' of the Nature (i.e., minimality or maximality of the necessary action) depends on the form of the mirror. The details of the dispute and some other interesting facts can be found in [44].
D'Arcy in his examples showed that the maxima of a functional can appear in Nature as well as minima of the same functional (by the way, Euler already understood this). But it is well-known that the critical points do not consist only of global maxima and global minima: there are local maxima and minima and saddle points also. As a standard example containing all possible types of critical points, one can take the geodesics on Riemannian manifolds.
3 When we speak about a mapping from one network G1 G1® X to another one G2 G2® X we mean the corresponding mapping of the sets {(g,Gi(g))}.
4 By assumption, V is the unique vertex from p-1(p(V)) which is not moved during the deformation Ft.