Overview:

Introduction Slideoperation quadratic lower bound quadratic upper bound

> <

Introduction

Let S be a set of n points in the Euclidean plane.
W.l.o.g. we assume that no two points of S have the same x-coordinate.
A crossing-free spanning tree of S is a tree whose edges connect all points in S with straight line segments that pairwise do not cross.
With T_S we denote the set of all crossing-free spanning trees of S.

Question: Whether, and how fast, can two members of T_S be transformed into each other by means of predefined rules, often called flips.
edge move: two trees in T_S have all but one edge in common (one edge is 'flipped').

[Avis, Fukuda 96]: The tree graph is connected and has a diameter bounded by 2n-4.
> <

Edge slide operation

[Goddard, Swart 96]: local edge move that keeps one endpoint of the moved edge fixed and moves the other one along an adjacent tree edge in continuous way.
=> continuous deformation of crossing-free spanning trees into each other.


> <




Question: How fast can two crossing-free spanning trees of T_S can be transformed into each other by means of the edge slide operation.
The tree graph TG(S) is an undirected graph that has T_S as its set of nodes. It realizes an arc between two nodes (trees) T' and T'' if and only if T' can be transformed into T'' by an edge slide.

[Aichholzer, Aurenhammer, Hurtado 00]: TG(S) is connected.

Conjecture: If two trees are part of the same triangulation of S then they can be transformed into each other by O(n²) edge slides.
By results in [AAH00], this would give a diameter of O(n² log n) for the corresponding tree graph.


> <

Main results

Theorem 1
Let T' and T'' be any two crossing-free spanning trees of S. Then T' can be transformed into T'' by O(n²) edge slides.

Theorem 2 Let T={p1-p2-...-pn} for odd n>2 have the shape of a spiral numbered from inside to outside. Then we need at least (n-1)(n-2)/2 edge slides to get a tree containing the edge (pn-2,pn).

> <

Proof of Theorem 1:

The weight of an edge e=(p_i,p_k) is the number of points in S which lie between the endpoints of e in the x-sorted order. The weight of a tree T, denoted by w(T), is the sum of the weights of its edges. w(T) < n²



Lemma 1 Any crossing-free spanning tree T in T_S can be transformed into an x-sorted path by at most 2w(T) edge slides.
> <

Rule 1

If there is an empty triangle (p_i,p_j,p_k) with (p_i,p_j) and (p_j,p_k) in T, where p_j has the smallest (resp. biggest) x-coordinate, then slide the longer (with respect ot the x-coordinate) edge.

This reduces w(T) by at least 1.
There are Situations, where Rule 1 is not aplicable.

> <

Rule 2 (more general)

If there is an empty triangle (p_i,p_j,p_k) with (p_j,p_k) in T, where p_j has the smallest (resp. biggest) x-coordinate and there is an x-monotone path of length k from p_i to p_j forming a simple polygon without interior points,

then slide all edges towards (p_i,p_j) (k-1 slides) then slide the long edge then reverse the k-1 slides. In total 2k-1 slides reduce the weight by k.
> <

Claim: Rule 2 is always applicable
Not monotone => point with 2 edges to the same side
Take longer of these and nearest point as new triangle.
> <

Lemma 2 The weight is bounded by w(T) < (3n2-10n+8)/4. This bound is tight.

Corollary: For any pair T', T'' in T_S we can transform T' into T'' by by at most 2(w(T') + w(T'')) < 3n²-10n+8.

> <

Theorem 2 Let T={p₁-p₂-...-p_n} for odd n>2 have the shape of a spiral numbered from inside to outside. Then we need at least (n-1)(n-2)/2 edge slides to get a tree containing the edge (p_n-2,p_n).

Proof: n=3 => 1 move. By induction we need at least (n-3)(n-4)/2 edge slides to get the edge (pn-4,pn-2). The yellow face contains n-3 inner edges => 2n-5 moves necessary. (n-3)(n-4)/2 + 2n-5 = (n-1)(n-2)/2

> <

Open problems

What is the complexity of finding the exact distance of two trees?

How fast can we compute a direction to minimize the weight of a given tree? (< O(n² log n))








> <


> <

> <

---

Last modified: by Klaus Reinhardt