# Find symmetries of a tree

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them). The sectors live in the complex plane, and for n even, sector 0 and n/2 are bisected by the real axis, and the sectors are evenly spaced.

These branches meet at certain points, called junctions. Each junction is adjacent to a subset of the sectors (at least 3 of them).

Specifying the junctions, (in pre-fix order, lets say, starting from junction adjacent to sector 0 and 1), and the distance between the junctions, uniquely describes the tree.

Now, given such a representation, how can I see if it is symmetric wrt the real axis?

For example, n=6, the tree (0,1,5)(1,2,4,5)(2,3,4) have three junctions on the real line, so it is symmetric wrt the real axis. If the distances between (015) and (1245) is equal to distance from (1245) to (234), this is also symmetric wrt the imaginary axis.

The tree (0,1,5)(1,2,5)(2,4,5)(2,3,4) have 4 junctions, and this is never symmetric wrt either imaginary or real axis, but it has 180 degrees rotation symmetry if the distance between the first two and the last two junctions in the representation are equal.

Edit: Here are all trees with 6 branches, distances 1. http://www2.math.su.se/~per/files/allTrees.pdf

So, given the description/representation, I want to find some algorithm to decide if it is symmetric wrt real, imaginary, and rotation 180 degrees. The last example have 180 degree symmetry.

Edit 2: If all length of the distances between the junctions were all the same, it is quite easy to find the reflection/rotation of a tree. The problem arises when the distances are of unequal length.

Notice that if I have a regular n-gon, with some non-intersecting chords, is sort of the dual to my trees. I use this in the drawing algorithm, for those that wonder.

That is, I create the n roots of unity (possible with some rotation), then the angle between junction (123) and (345) would be the same as for the mean of vertices 1,2,3 to the mean of vertices 3,4,5 in this n-gon.

The angles in the drawing is not really important, you may change the angles, but the order of the long branches should be the same, and you cannot rotate the tree.

EDIT 3:

Observe that there are many ways of drawing the trees. What I have is an equivalence relation, T1 ~ T2 if the two trees have the same junction representation. If S is an axis symmetry, or rotation by 180 degrees, Then S(T1) ~ S(T2), so the notion of being the same tree is well-defined. The question is therefore, how to determine if S(T1) ~ T1, or even better, compute S(T1). By above, this is independent on how I draw the tree.

• Sorry - it sounds very interesting but I cannot say what is it about. Maybe You could prepare some pictures? – kakaz May 1 '10 at 18:58
• Ok, I have added three examples. – Per Alexandersson May 1 '10 at 21:24
• I for one am intrigued but I just can't figure out what this is about. The description seems down on my level but for some reason I just don't get it. I can't reconcile even the first paragraph with the given examples. Clearly I am missing something as I stare at the first diagram while reading and re-reading "for n even, sector 0 and n/2 are bisected by the real axis". Help? – I. J. Kennedy May 2 '10 at 0:38
• I guess the beginning of your question is clearer when speaking of a partition (up to a set of measure zero) of the complex plane into a finite number of unbounded convex regions with boundaries given by piecewise linear curves. You get then indeed a tree with all leaves "at infinity". I understand then that you prescribe the lengths (in $\mathbb R_{\geq 0}\cup\infty$) of shared boundaries, labelling your connected components counterclockwise and you ask if such a configuration can be realized with a given symmetry? – Roland Bacher May 3 '10 at 13:47
• @roland-bacher Not really, given such partition, (with the datastructure as described), is there an "easy" way to decide if it has for example conjugation symmetry? By easy, I mean that I don't need to realize the datastructure as points in the plane, and literally look for the symmetry (this is a method I have an algorithm for, but explicitly drawing the tree just for searching for a symmetry is incredible stupid). – Per Alexandersson May 3 '10 at 14:58

## 2 Answers

I don't understand how the angles of the connecting finite segments are determined, so I'll assume the angles are set so that they don't break any symmetry. First observe that the reflection wrt the real axis sends sectors 0,1,2,3,4,5 to 0,5,4,3,2,1 respectively. So in your second example, tree

(0,1,5)(1,2,5)(2,4,5)(2,3,4) turns into

(0,5,1)(5,4,1)(4,2,1)(4,3,2)

which is different from the original tree (the original and transformed tree share only the first and last junction). So the transformation is not a symmetry of the tree. However, the same transformation sends the first example

(0,1,5)(1,2,4,5)(2,3,4) to

(0,5,1)(5,4,2,1)(4,3,2)

which is the same tree, represented in a non standard way because the junctions appear in the wrong order and the sectors of each junction are also in the wrong order.

Rotation of 180 degrees sends 0,1,2,3,4,5 to 3,4,5,0,1,2 (add 3 mod 6) so

(0,1,5)(1,2,5)(2,4,5)(2,3,4) turns into

(3,4,2)(4,5,2)(5,1,2)(5,0,1)

which is the same tree, again represented in a non standard way (the junctions appear in the inverse order, and each junction has its inciding sectors cycled).

So the recipe seems to be the following: Find out, for your transformation of the plane, which sectors goes to which, apply this permutation to the tree representation, and then reorder each tree representation (original and transformed) in a standard way that allows to compare if they are equal. If they are equal, then (assuming the angles are nice), the transformation of the plane is a symmetry of the tree. If they are not equal, then the transformation is not a symmetry of the tree.

• Yep, I got so far as well. The problem is when the length between the junctions are of unequal lengths. Some segments are mapped to themselves, and thus, its length does not matter. However, segments that are not mapped to themselves, must be mapped to segments of equal length, if the tree is symmetric. It is here I get into trouble, what does the transformation do to the list of distances? – Per Alexandersson May 3 '10 at 14:55
• Well, we need at least to have the distances in the presentation (and also the angles of the connecting segments). I don't understand how you generate the drawings without this data in the presentation of the tree. – Marcos Cossarini May 4 '10 at 5:19
• For example, in the second drawing of the linked file, the direction of the middle connecting segment seems strange for me. – Marcos Cossarini May 4 '10 at 5:25

but the order of the long branches should be the same, and you cannot rotate the tree.

So 'order' has nothing to do with the geometrical length, right? It is the depth of the tree that you are talking about?

It seems that the identity of a junction is its angular order (0 <= j < n), its position in the tree (using some traversal), and the quadrant of the complex plain it inhabits. It seems like the quadrant is totally determined by the angular order (j in my diagram):

{ { (n/4 <= j < n/2) (-/+), (j < n/4) (+/+) }, { (n/2 <= j < 3n/4) (-/-) , (3n/4 < j < n) (+/-)} }

• No, by order, I mean that rotation of the tree is not permitted. I should probably not have used that word, it appears in this context, but is not required for this discussion. Yes, the junctions are represented by what sectors (quadrants) they are adjacent to, and the order of the junctions in the representation is determined by traversing the tree counterclockwise. – Per Alexandersson May 11 '10 at 20:12