4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It's easy to make the "rotate" operation run fast if you're willing to allow the "lookup" operation (where you find a node and return its position) to be slower (e.g., proportional to the depth of the tree). Are you OK with that? Are you guaranteed that the depth of the tree will be logarithmic? If not, I'm not sure you can have any hope of a guarantee to retrieve the position of leaves in log time, as it takes time proportional to the depth of the tree just to find a leaf node. Are you allowed to rebalance or reorganize the tree, or is the tree structure fixed and not allowed to be changed? $\endgroup$ – D.W. Sep 18 '18 at 1:21
  • $\begingroup$ I am not guaranteed that the depth is logarithmic, that's what the last paragraph of my question is about. I am given a tree of points in space representing some crane-like object as explained above. (The original representation of the data is not imporant.) I may then store these points in any data structure (the process of converting the data to my data structure is not important too), that would allow me to perform the two mentioned operations as efficient as possible (that's important). I have no strict limits on the time complexities. $\endgroup$ – McSim Sep 18 '18 at 18:01
  • $\begingroup$ In other words: I have a general tree (no limits on the structure). parent -> subtree relation means "positions of all nodes in the subtree are dependent on the parent's rotation". I need to come up with a (possibly different) structure to store this information, that would give me the mentioned operations. $\endgroup$ – McSim Sep 18 '18 at 18:07
  • $\begingroup$ If i understand this correctly, 1) You want to store points in a tree structure (Need not be balanced) 2) Each point along with its tree can rotate about itself by a certain angle 3) After a certain number of rotations, you want the final position of a certain point? $\endgroup$ – RandomPerfectHashFunction Sep 18 '18 at 19:54
  • $\begingroup$ 2) and 3) are correct. 1: Input is a (not balanced) tree, but I may store it in any structure I want. And I need this structure to provide the two mentioned operations. $\endgroup$ – McSim Sep 18 '18 at 20:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But doesn't the index tree have a space complexity of $O(n^2)$? Its like the classical tug-of-war between space complexity and time complexity all over again. $\endgroup$ – RandomPerfectHashFunction Sep 18 '18 at 21:22
  • $\begingroup$ Wow. I am seriously surprised by this answer. It's exactly what I needed - a different approach to storing the relations between the nodes to give me efficient algorithms for the mensioned operations. I didn't think of using linear algebra to solve this (even though it's obviously a linear algebra related problem). You explained it really well and I even learned some new concepts. I will look into the heavy-light decomposition and update if I manage to get it right. $\endgroup$ – McSim Sep 18 '18 at 22:08
  • $\begingroup$ I can't deduce the space complexity right now without looking more deeply into it, but I'm OK with sacrificing a little space for the time. $\endgroup$ – McSim Sep 18 '18 at 22:18
  • $\begingroup$ And just one thing, you forgot one '*' character for bold :) I cannot edit it though, as it needs at least 6 characters changed. $\endgroup$ – McSim Sep 18 '18 at 22:29
  • $\begingroup$ @RandomPerfectHashFunction, nope (but I can see why you would be concerned, as it does require some analysis to justify why the space complexity is not too large). It turns out that the space complexity is $O(n)$. In the warmup, the space complexity for a index tree on $n$ nodes is $O(n)$. In the general case, suppose we have $k$ heavy paths, of size $n_1,\dots,n_k$. Then we know $n_1+\dots+n_k \le n$. Also the index trees for those heavy paths have size $O(n_1),\dots,O(n_k)$, respectively. Thus the total space usage for all index trees is $O(n_1+\dots+n_k)=O(n)$. $\endgroup$ – D.W. Sep 18 '18 at 22:51
2
$\begingroup$

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)
 }
$\endgroup$
  • $\begingroup$ What is the running time of your solution? Can all operations be supported in $O(\log n)$ time, as requested in the question, where $n$ is the number of points in the tree? I'm having a hard time reading your pseudocode, but I suspect that your code for calculateResultantCoordinates takes $O(d)$ time, where $d$ is the depth of the tree. This doesn't meet the requirements, as the tree might not be balanced and $d$ might be much larger than $\lg n$, so it is slower than what the question asked for. (In contrast, my answer avoids that problem.) $\endgroup$ – D.W. Sep 18 '18 at 20:48
  • $\begingroup$ @D.W. Im having a hard time formatting it. Gimme some time untill it get it right. And for time complexity, yes it would be $O(d)$. Im thinking of a better solution. $\endgroup$ – RandomPerfectHashFunction Sep 18 '18 at 20:59
  • $\begingroup$ @D.W. If insertions and deletions are allowed to be performed at any time, then a dynamic QuadTree is the only solution. Plus, no balancing can be done upon the tree (using K-D-B trees), since reordering of nodes in the tree are restricted by the hierarchy by which they appear in the tree i.e. If child P1 is attached to parent P2, then P1 will rotate about P2, when P2 rotates by an angle. So a $O(d)$ solution is the best solution for a dynamically changing QuadTree. $\endgroup$ – RandomPerfectHashFunction Sep 18 '18 at 22:01
  • $\begingroup$ This does what I need, however it's the straightforward approach, that I wanted to avoid, and come up with something outside the box, that could be more efficient. $\endgroup$ – McSim Sep 18 '18 at 22:12
  • $\begingroup$ Sorry, I didn't notice the previous comment. I don't need it to be dynamic necessarily. I will add that note to my question. $\endgroup$ – McSim Sep 18 '18 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.