A quadratic distance bound on sliding between crossing-free spanning trees

A quadratic distance bound on sliding between crossing-free spanning trees Oswin Aichholzer a,1and Klaus Reinhardt b aInstitute for Softwaretechnology Graz University of Technology, Austria bWilhelm-Schickard-Institut f¨ur Informatik Universit¨at T¨ubingen, Germany Abstract Let Sbe a set of npoints in the plane and let TSbe the set of all crossing-free spanning trees of S. We show that any two trees in TScan be transformed into each other by O(n2) local and constant-size edge slide operations. No polynomial upper bound for this task has been known, but in [1] a bound of O(n2log n) operations was conjectured. Key words: crossing-free spanning tree, local transformation, edge slide 1. Introduction Let Sbe a set of npoints in the Euclidean plane. W.l.o.g. we assume that no two points of Shave the same x-coordinate, otherwise we rotate the coordinate system appropriately. A crossing-free spanning tree of Sis a tree whose edges connect all points in S(and no others) with straight line segments that pairwise do not cross. With TSwe denote the set of all crossing-free spanning trees of S. An interesting question is whether, and how fast, two members of TScan be transformed into each other by means of predefined rules, often called flips. A common operation is what is called an edge move, which relates two trees in the set TSiff they have all but one edge in common (one edge is ‘flipped’). For this general setting Avis and Fukuda [2] showed that the corresponding tree graph is connected and has a diameter bounded by 2n−4. If we restrict the set of allowed flips to planar, length-improving edge moves then in [1] a way to transform any tree T∈ TSinto the mini- Email addresses: [email protected] (Oswin Aichholzer), [email protected] (Klaus Reinhardt). 1Research supported by Acciones Integradas 2003-2004, Proj.Nr.1/2003 mum spanning tree of Sin only O(nlog n) steps was given. For a more detailed discussion and some historical background see [1]. Our interest is focused on a local edge move that keeps one endpoint of the moved edge fixed and moves the other one along an adjacent tree edge. Following [3], we will call this constant-size operation an edge slide. More formally the central operation we consider is defined as follows [1]: Consider a tree T′∈ TS. A (planar) edge slide on T′takes some edge e∈T′and moves one of its endpoints along some edge adjacent to ein T′, without generating any edge crossings. This gives a new edge fand a new tree T′′ =T′∪ {f} \ {e}such that T′′ ∈ TS. An edge slide is a special kind of planar edge move: T′′ is obtained by closing with fa 3- cycle Cin T′and by removing efrom C, in a way such that T′avoids the interior of the triangle C. Intuitively speaking, an edge slide is an edge operation as local as it can be. In this paper we investigate the questions of how fast two crossing-free spanning trees of TS can be transformed into each other by means of the edge slide operation. To this end consider the tree graph TG(S) which is an undirected graph that has TSas its set of nodes. It realizes an arc between two nodes (trees) T′and T′′ if and only 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry if T′can be transformed into T′′ by an edge slide (and vice versa). In [1] it was shown that TG(S) is connected. The length of a shortest path in TG(S) corresponds to the distance between the two respective trees. However, for the edge slide operation no polynomial upper bound on this length has been known. It was conjectured that ‘if two trees are part of the same triangulation of Sthen they can be transformed into each other by O(n2) edge slides’. By results in [1], this would give a diameter of O(n2log n) for the corresponding tree graph TG(S). We are able to prove the following, stronger result: Theorem 1 Let T′and T′′ be any two crossingfree spanning trees of S. Then T′can be transformed into T′′ by O(n2)edge slides. As mentioned in [1] the edge slide operation could also prove useful in enumerating all simple polygons on a point set Svia constant-size local transformations. This question is still unsettled; see e.g. Hernando et al. [5]. Our upper bound on the diameter of TG(S) might be useful in this respect. 2. Upper Bound Construction Let Sand T∈ TSbe as defined in Section 1. We call a pair (e, pj), where e=pipkis an edge of Tand pi, pj, pk∈Sare sorted in x-order, a slide triangle if the open triangle ∆ = pipjpkis free of points from Sand edges from T, that is, the interior of ∆ is empty. q e’ e’’ p p’ p’’ (e’,p) Fig. 1. A slide triangle (e′, p), see Lemma 2. Lemma 2 Let Pbe a simple polygon with vertex set S, and let δP be the boundary of Pwith one marked edge e∗. If δP \ {e∗}is no x-monotonous path then in the interior of Pthere always exists a slide triangle (e, p)⊂P,e6=e∗. Proof Since δP \ {e∗}is not x-monotonous there exists a vertex q∈Swith two edges from δP \ {e∗}both emanating to the same side, i.e., both to the left or right of q. Let e′and e′′, respectively, be these edges. W.l.o.g. we assume that they emanate from qto the left, e′lies below e′′ and the left endpoint p′of e′lies to the left of the left endpoint p′′ of e′′, see Figure 1 (all other cases are symmetric). If the open triangle ∆ = qp′p′′ is empty we have a slide triangle (e′, p′′). Otherwise consider the point pwhich among all points of P in the interior of ∆ minimizes the angle ∠pp′qat p′. Note that there are no edges (partially) inside ∆ that have qas an endpoint or intersect e′or e′′. Therefore pprovides a slide triangle (e′, p). ✷ (a) (b) (c) Fig. 2. Cutting a tree polygon (a) along interior edges (b) to obtain a simple polygon (c). Atree polygon Pis a simple polygon with interior points, each point connected to the boundary δP via a unique (simple) path such that the resulting graph is planar, see Figure 2(a). In other words, the graph without the edges of δP is a forest. We claim that we can handle this more general situation like a simple polygon: Cut along interior edges and move them apart at the cuts infinitesimally, i.e., duplicate the related vertices, see Figure 2(b) and (c). Observe that the proof of Lemma 2 still holds for this setting by considering edges e′and e′′ that are neighboring in the cyclic order around q. We call the x-monotonous path connecting all vertices of Sin their x-sorted order the canonical spanning tree Tc∈ TSof S. Theorem 3 For a point set Sand a crossing-free spanning tree T∈ TS,T6=Tc, there always exists a slide triangle (e, p),p∈Sand e∈Tsuch that the path π∈Tconnecting pto e, say at point q, is x-monotonous. Moreover π∪pq is a simple polygon without interior points. March 25-26, 2004 Seville (Spain) Proof We first show that there always exists some slide triangle (e, p). The union of Tand the boundary of the convex hull of Spartitions Sinto k≥1 tree polygons Pi,i= 1,...,k. Since Tis a connected spanning tree each Pihas a unique edge which stems from the boundary of the convex hull of S. We mark these edges. From Lemma 2 and the discussion afterwards we know that we get a slide triangle inside some Piunless for all Pithe remaining (non marked) part is x-monotonous. But in the latter case Tmust be x-monotonous, too, that is, T=Tc, a contradiction. e p q π P Fig. 3. A path πconnecting pto q. Let qbe the (first) endpoint of eto which p is connected. If the edge pq belongs to Twe are done. Thus assume that pis connected to qvia a path πof length greater than 1, see Figure 3. Since (e, p) is a slide triangle the edge pq does not cross an edge of T. Thus the ‘pocket’ formed by πtogether with the edge pq and possible interior edges and points is a tree polygon P. If δP \pq is an x-monotonous path we are done. Otherwise we mark the edge pq and apply induction on P. Note that only one edge of Pis marked, since Tdoes not contain cycles. Moreover, in every induction step we obtain a smaller instance, since we get rid of at least one edge of T.✷ For an edge eits weight is defined as the number of points from Swhich lie in the open x-interval spanned by e, that is, the number of points which lie between the endpoints of ein the x-sorted order. The weight of a tree T, denoted by w(T), is the sum of the weights of its edges. Obviously Tchas weight zero and is the only tree with this property. Since each of the n−1 edges of Thas at most weight n−2 the weight of a tree with n points is bounded by (n−1)(n−2) < n2. A tight bound is given by the following lemma, for which we omit the proof in this extended abstract. Fig. 4. A tree with maximum weight of 3n2−10n+8 4. Lemma 4 The weight w(T)of a crossing-free spanning tree T∈ TSis bounded by 0≤w(T)≤ ⌊3n2−10n+8 4⌋,n≥2, and these bounds are tight. Lemma 5 Any crossing-free spanning tree T∈ TS can be transformed into Tcby at most 2·w(T)edge slides. e p p’ e’ q π Fig. 5. A slide triangle (e, p) with x-monotonous path π connecting pto q. Proof If T=Tcthe statement is obviously true, so let T6=Tc. Let (e, p) be a slide triangle as provided by Theorem 3, see Figure 5. Let k≥1 be the number of edges of the x-monotonous path πconnecting pto some endpoint qof e. We claim that we can reduce the weight of eby at least kby performing 2k−1 edge slides. To this end let e′be the edge of πincident to q. Our first task is to slide e′ along πto obtain the edge qp. Assume that k > 1. Then πavoids the interior of the slide triangle (e, p) and thus contains at least one vertex p′pointed away from the edge qp. Since πis x-monotonous we can slide the edge of πwhich has p′as its left endpoint ‘towards’ palong the edge of πwhich has p′as its right endpoint. We repeat this process until we obtain the edge qp, i.e., k= 1. Since each edge slide reduces the length of the current path from pto qby one, we carry out exactly k−1 steps. Now we can slide ealong qp, reducing its weight by at least k(the vertices of πdifferent from q). Finally we slide qp back to e′by reversing the steps of the first phase. 20th European Workshop on Computational Geometry As long as the resulting tree is not Tcwe repeat all above steps. After each iteration the weight of a single edge has been decreased by at least half of the number of the involved edge slide operations. We thus can transform Tinto Tcwith at most 2w(T) edge slides. ✷ We are now ready to prove our main result as proposed in Section 1. We give here a more explicit statement and Theorem 1 then follows as a corollary. Theorem 6 For any pair T′, T ′′ ∈ TSwe can transform T′into T′′ by at most 2(w(T′) + w(T′′)) ≤3n2edge slides. Proof Lemma 5 shows that we can transform any tree T′∈ TSinto Tcwith at most 2w(T′) edge slides. By symmetry of the edge slide operation we can use the reverse transformation for T′′. Together with the upper bound w(T′), w(T′′ )≤3n2 4 from Lemma 4, the theorem follows. ✷ p 1 p n−1 p n−4 p n−2 p n−3 p n Fig. 6. To obtain the edge pnpn−2requires (n−1)(n−2)/2 edge slides for odd n≥3. Figure 6 shows that there are examples requiring Ω(n2) edge slides to transform two spanning trees into each other. Thus the bound of Theorem 1 is tight. We omit the details on the lower bound construction in this extended abstract. 3. Discussion and Open Problems One might wonder whether the slide-distance between two spanning trees which do not intersect each other is smaller than in the general case. A similar result holds for triangulations, where the flip-distance can be bounded by the number of crossing edges [4]. However, from the example in Figure 6 it follows that even for two trees differing in only one edge the slide-distance is quadratic. Another observation is that the weight of a spanning-tree is direction-sensitive. So an obvious question is whether there always exists a ’nice’ direction with sub-quadratic weight? Again a negative answer is given by the example of Figure 6, having weight Θ(n2) for any direction of the x-axis. So far we only obtained results on the number of necessary slide operations. On the algorithmic side we are also interested in the time complexity to compute the O(n2) slide sequence. We plan to investigate this question in the near future. A related algorithmic question is how fast we can compute a direction to minimize the weight of a given tree. This can be done in time O(n2log n), but we omit the details in this extended abstract. Acknowledgments We would like to thank Ferran Hurtado for his presentation ‘Flip’ as the Paul Erd¨os lecture at CCCG 2003 in Halifax, Canada. This inspired us to (continue) work on the presented topic. We are grateful to Franz Aurenhammer and Hannes Krasser for enjoyable discussions and carefully reading the manuscript. References [1] O.Aichholzer, F.Aurenhammer, F.Hurtado Sequences of spanning trees and a fixed tree theorem. Computational Geometry: Theory and Applications, 21(1-2):3–20, 2002. [2] D.Avis, K.Fukuda Reverse search for enumeration. Discrete Applied Mathematics 65: 618-632, 1996. [3] W.Goddard, H.C.Swart Distances between graphs under edge operations. Discrete Mathematics 161: 121–132, 1996. [4] S.Hanke, T.Ottmann, S.Schuierer The edge-flipping distance of triangulations. Journal of Universal Computer Science 2 (1996), 570-579. [5] M.C.Hernando, M.E.Houle, F.Hurtado On local transformation of polygons with visibility properties. Proc. 6th International Computing and Combinatorics Conference COCOON’00, Springer LNCS 1858: 54–63, 2000.