Data structure for a tree of points moving in space

Question

I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "joints". Joints contain information about their position and their axis of rotation: Whole subtrees may rotate around their parent joint's axis by any given angle.

The described tree can be treated as the input. I need to store this data in some data structure, that would provide these two operations as efficient as possible:

• rotate(id, angle): Rotate a given joint with its subtree by a given angle around its parent's axis.

• get_position(id): Retrieve the current position of a joint (including leaves) by its id.

(The id may be the original coordinates, some arbitrary integer stored inside the joint etc.)

There are no strict limits on the time complexities of these operations. But obviously I'm looking for a complexity better than linear (logarithmic would be ideal), as that could be achieved with a straightforward approach. Neither there are any strict limits on space complexity. This structure doesn't have to be dynamic necessarily: I don't need insert or delete operations, I only need to store the information about the joints once.

The input tree is not balanced, and there is no way to balance it, as it would loose information about the subtrees' dependencies. So I thought the natural approach would be to construct a different tree structure with some relation other than simply parent node -> subtree as joint -> joints dependent on its rotation. But what relation could give me some good results?

Answer 1

You can solve this with a heavy-light decomposition of the tree. This will give you a data structure where the "rotate" operation runs in $O(\log n)$ time and the "retrieve position of leaf" operation runs in $O(\log^2 n)$ time, where $n$ is the number of nodes in the tree. Heavy-light decomposition is a big cannon, so it's possible there might be some simpler solution, but this should work. Let me explain the ideas in several steps.

Closure property of affine transformations

If $T$ is a a rotation around some point in space, note that it can be represented as an affine transformation. Also, the set $\mathcal{T}$ of affine transformations is closed under composition. In particular, if $T_1,T_2$ are two affine transformations, let $T_2 \circ T_1$ denote the result of first applying transformation $T_1$, then applying transformation $T_2$; then $T_2 \circ T_1$ is itself an affine transformation, and its parameters can be efficiently computed from the parameters of $T_1,T_2$. So, if we have a sequence of transformations that should be applied to a point, we can concisely represent the composition of the sequence of transformations by $O(1)$ parameters (namely, the parameters of their composition). This will be useful in a moment.

In particular, rather than updating the position of individual nodes, we will store information to help us recover the transformation that should be applied to any particular node. When we want to retrieve up the location of a node, we first look up this transformation, then apply it to the original location of that node to obtain its current location, and output that.

Warm-up: a path

As a warm-up, let's consider the most extreme special case of your situation: where the tree is a path of length $n$, i.e., each node has exactly one child, and there is a single leaf. I'll assume each node in this original tree may have a position associated with it.

Data structure. We can build a data structure for this case where all operations run in $O(\log n)$ time. Build a complete binary tree (of height $\lceil \lg n \rceil$) over these $n$ nodes; to give it a name distinct from your original tree, call this the "index tree". Each node of the original tree is a leaf in the index tree. Each node $w$ of the index tree corresponds to a consecutive subpath of the original tree/path (namely, the ones corresponding to the leaves of the index tree that are descendants in the index tree of $w$).

Now each node $v$ of the original tree has a transformation $T_v$ associated with it. Suppose a node $w$ of the index tree corresponds to the subpath of nodes $v_1,\dots,v_k$ in the original tree. Then we will label $w$ with the transformation $T_{v_k} \circ \cdots \circ T_{v_1}$. This will help us to retrieve the position of points in the original tree.

Rotation operations. To support rotation operations, if we want to rotate node $v$ in the original tree and all its descendents, then we follow the path (in the index tree) from $v$ to the root of the index tree. By construction, there are only $\lg n$ such nodes to visit. We'll need to update the label on each of these nodes in the index tree. That is easy. In particular, the label $T_w$ on each node $w$ in the index tree can be computed from the labels $T_{w_1},T_{w_2}$ on its two children $w_1,w_2$ as $T_w = T_{w_2} \circ T_{w_1}$. So, to handle a rotation operation on node $v$ in the original tree, we update the the label on $v$ in the index tree, then follow the path (in the index tree) from $v$ to the root of the index tree and recompute the label of each such node in the index tree. All of this can be done in $O(\log n)$ time.

Retrieval operations. If we want to retrieve the location of the point associated with node $v$ in the original tree, we can do that in $O(\log n)$ time, too. Consider the path in the original tree from its root to $v$. This is a subpath of the original tree. It turns out that it can be expressed as the disjoint union of $O(\lg n)$ subpaths, where each subpath corresponds to a node in the index tree. Let $w_1,\dots,w_k$ be those nodes in the index tree. Then the transformation that needs to be applied is $T_{w_k} \circ \cdots T_{w_1}$; we apply this to the original location of $v$, and output that. This can all be done in $O(\log n)$ time.

So this handles the case of a path, i.e., a tree of depth $n$. This shows that it is possible to handle imbalanced trees. But how do we handle the general case? I'll show that next.

General case: an arbitrary tree

To handle an arbitrary tree, we will first build a heavy-light decomposition of the tree. This expresses the edges of the tree as a union of (disjoint) heavy paths, plus some light edges; with the property that any path from the root to some leaf visits at most $O(\log n)$ light edges. We'll treat each individual heavy path as a case of the warmup above, i.e., we'll build one index tree per heavy path, to keep track of the transformations associated with the nodes in the heavy path. Also, we'll have a path tree that stores the light edges, and we'll store the transformation associated with the head of a light edge in that node of the path tree.

Rotation operations. To handle a rotation operation, we update the associated node in the path tree (if it is the head of a light edge) or do the appropriate update operation on the corresponding index tree (if it is the head of a heavy edge). This can be takes $O(\log n)$ time at worst.

Retrieval operations. To retrieve the location of a node $v$ in the original tree, we follow the path in the path tree from the root to $v$. This will involve traversing at most $O(\log n)$ light edges. It also traverses at most $O(\log n)$ heavy paths. In each heavy path, we might potentially traverse many vertices of the heavy path (possibly much more than $O(\log n)$ of them), but we don't need to visit all of them; since that is a consecutive subpath of the heavy path, we can quickly retrieve the transformation associated with that subpath (i.e., the composition of the transformations of the nodes in that heavy path) using the index tree for that subpath. This takes $O(\log n)$ time per heavy path, and there are at most $O(\log n)$ heavy paths to visit. Finally, we compose all of these transformations and apply it to the original location of $v$.

Naively, the running time seems to be $O(\log n)$ time for the light edges, plus $O(\log n) \times O(\log n)$ time for the heavy paths, for a total of $O(\log^2 n)$ time.

This achieves all of your goals, and gives a guaranteed worst-case running time of $O(\log n)$ for the rotate operation and $O(\log^2 n)$ time for the lookup operation, no matter what shape the original tree has.

Answer 2

As far as I understand your requirements,

1. You want to store a set of points in a tree, not necessarily balanced.
2. You want to be able to rotate any sub-tree about its root point, by any angle
3. You want to find the final coordinates of any point after after a set of rotation operations as specified above.

Since we'll be storing 2D points in a tree structure, I'll be using a point QuadTree approach to store the points. Let the structure of a node of the tree be as follows: $ Node := (x,y,\theta,q1,q2,q3,q4,parent)$. Where

• $x,y$ is the co-ordinate of a point.
• $\theta$ is the resultant angle by which the point's tree has been rotated to after an arbitrary number of rotation operations.
• $q1,q2,q3,q4$ are pointers to the quadrants with respect to $(x,y)$.
• $parent$ is a pointer to the parent node.

Functions for the QuadTree

1. $insertPoint(x,y)$
   This would be a standard QuadTree insertion algorithm while setting $\theta=0$ for the newly inserted node.

2. $searchPoint(x,y)$
   This would search the QuadTree for a node representing $(x,y)$ and return a pointer to it. This will be used ahead.

3. $rotatePoint(x,y,\theta)$
   This would be a standard QuadTree search for $(x,y)$. Then upon finding the particular node, set $node.\theta = node.\theta + \theta$ i.e. add and store the rotation angle into the $\theta$ value already in the node.

4. $calculateResultantCoordinates(x,y)$
   This is where the magic happens.
   This function will return a $(x',y')$ pair consisting of the resultant co-ordinates of the $(x,y)$ passed to the function.
   pseudo-code

calculateResultantCoordinates(x,y)
 {
  n = searchFor(x,y)
  if (n is null)
   // error handling

  (x,y)=(n.x,n.y)

  while ( n.parent != null )
    {
     if ( n.parent.theta == 0 )
       continue

     x = x - n.parent.x
     y = y - n.parent.y
     // (x,y) now represent a complex number (x + j*y)
     // rotating a complex number can be done by multiplying it with $e^{j*\theta}$ = $cos(\theta) + j*sin(\theta)$

     // the resultant point is
     // $(x*cos(\theta)-y*sin(\theta),x*sin(\theta)+y*cos(\theta))$
     p = x*cos(p.theta) - y*sin(p.theta)
     q = x*sin(p.theta) - y*cos(p.theta)

     (x,y) = (p,q)
     n = n.parent
     // traverse the path from leaf to the root node
    }

  return (x,y)
 }