| Sbornik: Mathematics |
|
|
|
|
|
Planar locally minimal trees with boundaries on a circle I. N. Mikhailov Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
Bibliographic databases:
     § 1. IntroductionThe well-known Steiner problem consists in seeking a shortest network spanning a finite set of points, which are called boundary points, in some ambient metric space. This problem is interesting first of all because of its numerous applications; in particular, it has a natural transport interpretation in the case of the ordinary Euclidean plane. In many classes of metric spaces the local structure of shortest networks is known. For example, on an arbitrary Riemannian manifold edges of networks of this kind are geodesics (see [1] and [2]) and meet at vertices at angles of at least $2\pi/3$. In particular, the degrees of all vertices are at most $3$. Without loss of generality we can also assume that networks of this kind do not contain nonboundary vertices of degree $2$, since geodesics meet at such points at an angle of $\pi$ and thus we can eliminate them from the vertex set by gluing the two incoming geodesics into a single one, which keeps the network to be shortest and does not change it as a subset of the manifold. In addition, by cutting an arbitrary shortest tree through boundary vertices of degrees above $1$, we can reduce the Steiner problem on a Riemannian manifold to the case of full Steiner networks, that is, networks such that their sets of boundary vertices coincide with the sets of vertices of degree $1$, and all nonboundary vertices have degree $3$. The problem of the construction of a shortest network spanning a given set of points is $\mathrm{NP}$-complex (see [3]) even in the discrete case when all points in the boundary set and in the network to be constructed are assumed to have integer coordinates, and it admits a polynomial solution algorithm only when the network topology is known. Hence the problem of the description of all shortest networks spanning a given set of points is generally very difficult. A natural extension of the class of shortest networks is the class of locally shortest networks, which are shortest in a neighbourhood of each point. Thus, these are precisely networks whose local structure is the same as that of shortest networks. In the case of the ordinary Euclidean plane, locally shortest networks are all possible planar graphs such that nonboundary vertices are of degree $3$, boundary vertices are of degree at most $3$, and edges are line segments that meet at vertices at angles of at least $2\pi/3$ (see [4] and [5]). Ivanov and Tuzhilin [1], [2] presented a full description of planar Steiner trees with convex locally minimal realizations, that is, planar trees that are planar equivalent to a full Steiner tree spanning the vertices of a convex polygon. In addition to trees with convex boundaries, Ivanov and Tuzhilin also studied trees with regular (see [6]–[8]) and quasi-regular (see [9]) boundaries whose boundary vertices lie at the vertices of a regular polygon or on the successive arcs of the circumscribed circle of a regular polygon, respectively. In this paper we consider planar trees having circular minimal realizations, or, more precisely, trees that are planar equivalent to some full Steiner tree spanning vertices of a convex inscribed polygon. A wide class of trees that have convex minimal realizations but do not have circular minimal realizations is described. AcknowledgmentsThe author is grateful to his scientific advisor A. A. Tuzhilin for posing the problem and his constant attention to this research and also to A. V. Begunts and S. V. Shaposhnikov for involving him in scientific work and for their assistance in his search for an appropriate research topic. § 2. Basic definitions and preliminary resultsWe give the basic definitions and assertions; for detail, see [1] and [2]. A planar graph is called a planar tree if the corresponding combinatorial graph is a tree. Note that when variational problems are studied, a finite subset of vertices, called boundary vertices, is distinguished on each tree, whereas other vertices are called interior vertices. Edges incident to at least one boundary vertex are also called boundary edges. A full Steiner tree is a planar tree such that all of its vertices have degree $1$ or $3$, the vertices of degree $1$ form the set of boundary vertices, and edges are line segments. A full Steiner tree is locally minimal if at all of its vertices of degree $3$ edges meet at an angle of $2\pi/3$. A full Steiner tree has a convex locally minimal realization if there exists a planar-equivalent locally minimal full Steiner tree such that all of its boundary vertices are at vertices of some convex polygon. A full Steiner tree has a circular minimal realization if it has a convex locally minimal realization such that all of its boundary vertices lie on some circle. A path $\gamma$ in a planar tree $G$ is called oriented if one of the two natural orderings is fixed on its vertices. We define oriented polygonal lines in a similar way. Note that edges of an oriented polygonal line can be considered as ordinary vectors on the plane. We let $(e_1, e_2)$ denote the sequence of edges of the unique oriented path in a full Steiner tree $G$ such that its first edge coincides with $e_1$ and its last edge coincides with $e_2$. It is sometimes convenient to regard an edge $e$ in $(e_1, e_2)$ as a nonoriented edge of the original graph; in such a case this will be clear from the context. By analogy, we let $(v_1, v_2)$ denote the sequence of vertices of the unique oriented path in a full Steiner tree $G$ such that its first and last vertices are $v_1$ and $v_2$, respectively. We fix the standard orientation on the plane. We consider an arbitrary oriented path $\gamma$ in a full Steiner tree $G$. We assign $+1$ to a pair of consecutive edges $e_1$, $e_2$ in this path if the basis consisting of $e_1$ and $e_2$ is positively oriented, and we assign $-1$ otherwise. The sum of these numbers over all pairs of consecutive edges in $\gamma$ is called the twisting number of $\gamma$ and is denoted by $\operatorname{tw}(\gamma)$ (or by $\operatorname{tw}(e_1, e_2)$, or $\operatorname{tw}(v_1, v_2)$ if the first and last edges in the path $\gamma$ are $e_1$ and $e_2$ or the first and last vertices of $\gamma$ are $v_1$ and $v_2$, respectively). The greatest of the twisting numbers $\operatorname{tw}(\gamma)$ over all oriented paths $\gamma$ in $G$ is called the twisting number of $G$ and is denoted by $\operatorname{tw}(G)$. We consider an arbitrary oriented polygonal line $X_1X_2\dots X_n$. The angle $\angle (X_iX_{i+1}, X_{i+1}X_{i+2})$ between two consecutive edges $X_iX_{i+1}$ and $X_{i+1}X_{i+2}$ of this line is the angle between the vectors $\overrightarrow{X_iX_{i+1}}$, $\overrightarrow{X_{i+1}X_{i+2}}$ taken with the plus sign if $\operatorname{tw}(X_iX_{i+1},X_{i+1}X_{i+2})=1$ and with the minus sigh otherwise. The angle of rotation $\operatorname{rot}(X_1X_2\dots X_n)$ along the line $X_1X_2\dots X_n$ is defined as the sum $\sum_{i=1}^{n-2}\angle (X_iX_{i+1},\,X_{i+1}X_{i+2})$. Note that in the case when $G$ is a locally minimal full Steiner tree, the angle between any two consecutive edges in an arbitrary oriented path $\gamma$ is $\pm\pi/3$, that is, $\operatorname{tw}(\gamma)= \operatorname{rot}(\gamma)/(\pi/3)$. We emphasize two elementary properties of the twisting number:
Now we state two key well-known propositions concerning full locally minimal trees. Proposition 1. If all vertices of degree $1$ of a full locally minimal Steiner tree lie on the boundary of a convex polygon, then the twisting number of $G$ is at most $5$. Proposition 2. Each full locally minimal Steiner tree lies in the convex hull of the set of its boundary points. The following two simple statements, which we use in what follows, are also true. Statement 1. If $G$ is a full Steiner tree, $\operatorname{tw}(G) \leqslant k$, and edges $e$ and $f$ of this tree satisfy $\operatorname{tw}(e, f)=k$, then $e$ and $f$ are boundary edges. Statement 2. Assume that a full Steiner tree with twisting number $\operatorname{tw}(G)=5$ satisfies $\operatorname{tw}(e, e')=(-1)^k\,5$, $k\in\mathbb{Z}$, where $f$ and $f'$ are the second and penultimate edges in the sequence $(e, e')$, and let $g$ and $g'$ be edges adjacent to the pairs of edges $e$, $f$ and $e'$, $f'$ respectively, but not coinciding with these edges. Then $ \operatorname{tw}(e, f)=\operatorname{tw}(g', f')=\operatorname{tw}(e', g')=(-1)^k$ and $\operatorname{tw}(e', f')=\operatorname{tw}(g, f)=\operatorname{tw}(e, g)= (-1)^{k+1}$. Finally, we will use the following well-known fact. Statement 3. The full angle of rotation along a closed non-self-intersecting polygonal line is $\pm2\pi$ depending on the direction chosen. § 3. Main resultHere we state and prove our main result. Theorem. Let $\gamma=v_1 e_1 \dots v_2 \dots v_3 \dots e_4 v_4$ be a path in a full Steiner tree $G$, where $v_1$, $v_2$, $v_3$ and $v_4$ are distinct vertices of $G$, and $e_1$ and $e_4$ are some edges of $G$. Let $e_2$ and $e_3$ denote the edges of $G$ that are incident to $v_2$ and $v_3$, respectively, but do not belong to $\gamma$. Assume that: Then the tree $G$ has no circular minimal realization. Proof. Suppose that a tree $G$ satisfying the assumptions of the theorem has a circular minimal realization; for convenience, we consider $G$ as coinciding with this minimal realization.
Since a circular minimal realization is convex, Proposition 1 and Statement 1 immediately yield that $e_1$, $e_2$, $e_3$ and $e_4$ are boundary edges of $G$. Proof. Suppose the converse. Let $f$ be the penultimate edge in the sequence $(e_1, e_2)$ and $f'$ be the second edge in the sequence $(e_2, e_3)$. Since we assume that ${\operatorname{tw}(e_1, e_2)=-5}$, we have $\operatorname{tw}(f, e_2)=-1$ by Statement 2; hence $\operatorname{tw}(e_2, f)=-\operatorname{tw}(f, e_2)=1$. However, by assumption (2) of the theorem $\operatorname{tw}(e_2, f')\geqslant 0$, that is, $\operatorname{tw}(e_2, f')=1$ since these two edges are adjacent. Thus, $\operatorname{tw}(e_2, f')=\operatorname{tw}(e_2, f)=1$, which implies that $f$ coincides with $f'$; this contradicts the fact that $f'$ and $f$ are consecutive edges in the path $\gamma$.
The lemma is proved. Proof. Suppose the statement is not true and $\operatorname{tw}(e_3, e_4)=5$ (Figure 1). Let $f$ be the penultimate edge in the sequence $(e_1, e_2)$, $f'$ be the second edge in the sequence $(e_2, e_3)$, $e$ be the penultimate edge in the sequence $(e_2, e_3)$, and $e'$ be the second edge in the sequence $(e_3, e_4)$.
It follows from Statement 2 that
$$
\begin{equation*}
\begin{gathered} \, \operatorname{tw}(f, e_2)=1, \qquad \operatorname{tw}(f, f')=-1, \qquad \operatorname{tw}(e_2, f')=1, \\ \operatorname{tw}(e_3, e')= 1, \qquad \operatorname{tw}(e, e')=-1, \qquad \operatorname{tw}(e_3, e)=-1. \end{gathered}
\end{equation*}
\notag
$$
We also have
$$
\begin{equation*}
\operatorname{tw}(f', e)=\operatorname{tw}(e_2, e)-\operatorname{tw}(e_2, f')= \operatorname{tw}(e_2, e)-1\geqslant 0-1=-1.
\end{equation*}
\notag
$$
If $\operatorname{tw}(f', e)=-1$, then
$$
\begin{equation*}
\operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, f')+\operatorname{tw}(f', e)+\operatorname{tw}(e, e_3)=1-1+1=1,
\end{equation*}
\notag
$$
which contradicts the assumptions of the theorem. Therefore, $\operatorname{tw}(f', e)\geqslant 0$. Then
$$
\begin{equation*}
\begin{aligned} \, \operatorname{tw}(e_1, e_4) &=\operatorname{tw}(e_1, f)+\operatorname{tw}(f, f')+ \operatorname{tw}(f', e)+\operatorname{tw}(e, e')+\operatorname{tw}(e', e_4) \\ &=4-1+ \operatorname{tw}(f', e)-1+4=6+\operatorname{tw}(f', e) \geqslant 6, \end{aligned}
\end{equation*}
\notag
$$
which, according to Proposition 1, contradicts the convexity of the realization under consideration. The lemma is proved. Lemma 3. The inequality $2 \geqslant \operatorname{tw}(e_2, e) \geqslant 0$ holds for any edge but $e_3$ in the sequence $(e_2, e_3)$. Proof. The second inequality holds by the assumptions of the theorem. We prove the first. Suppose there is an edge $h$ in the sequence $(e_2, e_3)$ distinct from $e_3$ and such that $\operatorname{tw}(e_2, h)=3$. Then $h$ is not a boundary edge; thus, $\operatorname{tw}(e_2, g)=4$, where $g$ is one of the edges adjacent to it. Then $\operatorname{tw}(e_1, g)=6$, which contradicts the convexity of the realization under consideration according to Proposition 1.
The lemma is proved. Proof. It follows from Lemma 3 that $\operatorname{tw}(e_2, e_3) \in \{-1, 0, 1, 2, 3\}$. The assumption (2) of the theorem implies that $\operatorname{tw}(e_2, e_3) \neq 1$ and $\operatorname{tw}(e_2, e_3)\neq -1$.
Let $e'$ be the second edge in the sequence $(e_3, e_4)$ and $e$ be the penultimate edge in the sequence $(e_2, e_3)$. Since $\operatorname{tw}(e_3, e_4)=-5$, we have $\operatorname{tw}(e_3, e)=1$ by Statement 2. Using the estimate $\operatorname{tw}(e_2, e)\leqslant 2$ from Lemma 3, we obtain
$$
\begin{equation*}
\operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, e)+\operatorname{tw}(e, e_3)= \operatorname{tw}(e_2, e)-1 \leqslant 2-1=1.
\end{equation*}
\notag
$$
Therefore, $\operatorname{tw}(e_2, e_3)$ is $0$.
The lemma is proved. Lemma 5. Let $P_1P_2\dots P_n$ be a convex polygon. Then all angles between consecutive edges of the polygonal line $P_1P_2\dots P_nP_1P_2$ are of the same sign. Proof. Without loss of generality we assume that the angle between $P_1P_2$ and $P_2P_3$ is positive, whereas the one between $P_2P_3$ and $P_3P_4$ is negative. Note that $P_4$ and $P_1$ are on opposite sides of the line $P_2P_3$ in this case. This is in contradiction with the fact that the polygon $P_1P_2\dots P_k$ is convex.
The lemma is proved. Lemma 6. Let $B$ be an arbitrary disc in the plane, $\partial B$ be the boundary of $B$, $X_1X_2\dots X_n$ be a non-self-intersecting polygonal line $\gamma$ lying in $B$ such that ${\gamma\cap\partial B=\{X_1, X_n\}}$, and let $\operatorname{rot}(\gamma)= 5\pi/3$. Then the rays $X_2X_1$ and $X_{n-1}X_n$ intersect outside $B$ at an angle of $2\pi/3$. Proof. We show that it is possible to inscribe polygonal lines $X_nP_1P_2\dots P_kX_1$ and $X_nQ_1Q_2\dots Q_lX_1$ in the two arcs $X_1X_n$ of $\partial B$ so that each of these lines intersects $\gamma$ only at the vertices $X_1$ and $X_n$.
For subsets $A$ and $B$ in a metric space, we let $\rho(A,B)$ denote the infimum of the distances between arbitrary points $a\in A$ and $b\in B$, that is, $\rho(A,B)= \inf\{|ab|\colon {a\in A,\,b\in B}\}$. We construct discs with centres $X_1$ and $X_n$ and radii below $\rho(X_1, \gamma\setminus[X_1X_2))$ and $\rho(X_n, \gamma\setminus[X_nX_{n-1}))$, respectively. We choose points $Q'$ and $P'$, and $Q_1$ and $P_1$ in the first and second discs, respectively, that lie on $\partial B$ in the same order in which the vertices $Q_k$, $P_l$, $Q_1$ and $P_1$ of the polygonal lines to be constructed must lie on $\partial B$. After that it suffices only to inscribe polygonal lines in the arcs $\mathop{\smallsmile} P_1P'$ and $\mathop{\smallsmile} Q_1Q'$ so that their endpoints coincide with the vertices of these arcs and they do not intersect $\gamma$. We construct a polygonal line of this type for the arc $\mathop{\smallsmile} P_1P'$. Since $\mathop{\smallsmile} P_1P'$ and $\gamma$ are disjoint compact sets, the distance $d$ between them is positive. We subdivide the arc $\mathop{\smallsmile} P_1P'$ into subarcs of length below $d$. Clearly, the endpoints of these subarcs arranged in the order from $P_1$ to $P'$ are the vertices of the required polygonal line. We consider the polygons $X_1X_2\dots X_nP_1\dots P_k$ and $X_1X_2\dots X_nQ_1\dots Q_l$ and orient their boundaries in accordance with the above orderings of their vertices. It follows from the construction of the polygonal lines that the boundaries of $X_1X_2\dots X_nP_1\dots P_k$ and $X_1X_2\dots X_nQ_1\dots Q_l$ are of opposite orientations. By Statement 3 the full angle of rotation of just one of these polygons along its boundary is $2\pi$. Without loss of generality we let $X_1X_2\dots X_nP_1\dots P_k$ be this polygon. We denote the angles between consecutive edges of the oriented polygonal line $X_{n-1}X_nP_1 \dots P_kX_1X_2$ by $\alpha,\psi_1,\dots,\psi_k$ and $\beta$, respectively. By the equalities $\operatorname{rot}(X_1X_2\dots X_nP_1\dots P_kX_1X_2)=2\pi$ and $\operatorname{rot}(\gamma)=5\pi/3$ we have $\alpha+\psi_1+\dots+\psi_k+ \beta=\pi/3$. Applying Lemma 5 to the convex polygon $X_nP_1\dots P_kX_1$, we conclude that all angles $\psi_1,\dots,\psi_k$ are of the same sign. From the construction of the polygonal line $X_nP_1\dots P_kX_1$ we see that $P_2$ does not lie on the arc $\mathop{\smallsmile}X_nP_1$ not containing $X_1$. Hence $P_2$ lies in the same half-plane as $X_{n-1}$ with respect to the line $X_nP_1$. It follows that the angles $\alpha$ and $\psi_1$ are of the same sign. Similarly, $\beta$ and $\psi_k$ are of the same sign. Therefore, all angles $\alpha,\psi_1,\dots,\psi_k$ and $\beta$ are of the same sign; by the above equality they are nonnegative. We calculate the sum of the angles of the polygon $X_nP_1\dots P_kX_1$ in two ways. On the one hand the sum of its angles is $\pi k$. On the other hand it is
$$
\begin{equation*}
\angle X_1X_nP_1+(\pi -\psi_1)+\dots+(\pi-\psi_k)+\angle P_kX_1X_n.
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\pi k=\pi k-(\psi_1+\dots+ \psi_k)+\angle X_1X_nP_1+\angle P_kX_1X_n.
\end{equation*}
\notag
$$
That is, we have
$$
\begin{equation*}
\angle X_1X_nP_1+\angle P_kX_1X_n= \psi_1+\dots+\psi_k.
\end{equation*}
\notag
$$
Since $\alpha,\beta\geqslant 0$, it follows that
$$
\begin{equation*}
\angle X_2X_1X_n=\pi-\beta-\angle P_kX_1X_n, \qquad \angle X_1X_nX_{n-1}=\pi-\alpha-\angle X_1X_nP_1.
\end{equation*}
\notag
$$
Then
$$
\begin{equation*}
\begin{aligned} \, \angle X_2X_1X_n+\angle X_1X_nX_{n-1} &=(\pi-\beta-\angle P_kX_1X_n)+(\pi-\alpha-\angle X_1X_nP_1) \\ &=2\pi-(\alpha+\beta+\psi_1+\dots+\psi_k)=2\pi-\frac{\pi}{3}=\frac{5\pi}{3}, \end{aligned}
\end{equation*}
\notag
$$
which implies that the rays $X_2X_1$ and $X_{n-1}X_n$ intersect at an angle of $2\pi/3$, as required.
Lemma 6 is proved. We return to the proof of the theorem. Let $B$ be the disc whose boundary contains the boundary vertices of $G$, and let the vertices of the edges $e_2$ and $e_3$ distinct from $v_2$ and $v_3$ be denoted by $w_2$ and $w_3$, respectively (Figure 2). Applying Lemma 6 to the polygonal line $(v_1,w_2)$ we infer that the rays outgoing from $v_1$ and $w_2$ and parallel to the edges $e_1$ and $e_2$, respectively, but not containing them intersect at an angle of $2\pi/3$ at some point $R$ outside $B$. Then the larger arc cut out on $\partial B$ by the sides of the angle $\angle v_1Rw_2$ is at least $4\pi/3$. Similarly, applying Lemma 6 to the polygonal line $(w_3,v_4)$ we infer that the rays from $w_3$ and $v_4$ that are parallel to the edges $e_3$ and $e_4$, respectively, but do not contain them intersect at an angle of $2\pi/3$ at some point $S$ outside the disc $B$ and that the larger arc cut out on $\partial B$ by the sides of the angle $\angle w_3Sv_4$ is at least $4\pi/3$. It follows from Lemma 4 that $e_2\parallel e_3$; therefore, the lines $Rv_2$ and $Sv_3$ are parallel. Let $f'$ be the second edge in the sequence $(e_2,e_3)$ and $w$ be the vertex distinct from $v_2$ of this edge. Since $\operatorname{tw}(e_1,e_2)=5$, we have $\operatorname{tw}(e_1,f')=3$. Thus, the vector $\overrightarrow{v_1R}$ is codirected with the vector $\overrightarrow{v_2w}$. It follows that $w$ and $v_1$ lie in distinct half-planes with respect to the line $v_2R$. Lemma 3 yields that all oriented edges in the sequence $(e_2,e_3)$ have directions such that their projections onto the ray starting on the line $v_2R$, orthogonal to it, and lying in the same half-plane as $w$ are nonnegative. Thus, all vertices but $w_2$ and $v_2$ of edges in the sequence $(e_2,e_3)$ lie in the distinct half-plane from $v_1$ with respect to the line $v_2R$. In particular, this is true for $v_3$. It follows from Lemmas 1, 2 and 4 that the vectors $\overrightarrow{v_1R}$ and $\overrightarrow{Sv_4}$ are codirected. Since $v_1$ and $v_3$ lie in distinct half-planes with respect to the line $v_2R$, the extension of the ray $v_1R$ beyond the point $R$ intersects the line $Sv_3$. This implies that the ray $Sv_4$ does not intersect the line $v_2R$, that is, the angles $\angle v_1Rv_2$ and $\angle v_3Sv_4$ have disjoint interiors. It follows that the arcs cut out on $\partial B$ by these angles are also disjoint. Then the length of the circle $\partial B$ is at least the sum of the lengths of the two larger arcs cut out on $\partial B$ by the sides of these angles, that is, it at least $2\cdot4\pi/3 > 2\pi$, which is a contradiction. The theorem is proved. Note that it is impossible to discard the condition $\operatorname{tw}(e_2, e_3)\neq 1$. Consider the tree $T$ shown in Figure 3. The equalities $\operatorname{tw}(e_1,e_2)=\operatorname{tw}(e_3,e_4)=5$ and $\operatorname{tw}(e_2,e_3)=1$ hold for it. We prove that it has a circular minimal realization. We let $l_1$ and $l_2$ denote the straight lines containing the boundary vertices of $T$ such that there are seven boundary vertices on $l_2$ ($l_2$ is on the right in Figure 3). We draw a circle $\omega$ that contains all vertices of $T$ but the boundary vertices lying on $l_2$ in its interior (the dashed line in Figure 3). We regard the points of intersection of $\omega$ with boundary edges of $T$ as new boundary vertices. Extending the boundary edges of the tree $T$ with vertices on $l_1$ until they intersect $\omega$ and also regarding the resulting points of intersection with $\omega$ as new boundary vertices, we obtain a new tree $T'$, which is planar equivalent to $T$ and all boundary vertices of which lie on $\omega$. Thus, $T$ has indeed a circular minimal realization. § 4. ConclusionsThe author looks forward to obtaining in the future a full classification of trees having circular minimal realizations by using the parquet techniques developed in [1], [2] and [6]. 
Citation in format AMSBIB
\Bibitem{Mik24} |
|
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|