patternMinor
Data structure for a tree of points moving in space
Viewed 0 times
spacepointsmovingforstructuredatatree
Problem
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:
-
-
(The
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
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
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?Solution
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 assoc
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 assoc
Context
StackExchange Computer Science Q#97460, answer score: 2
Revisions (0)
No revisions yet.