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 subtree under given joint by its id by a given angle around its 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?

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?

I'm trying to come up with a data structure for a following model: "Joints" (points in space) are structured like a tree (any tree). I want to be able to rotate whole subtrees of this tree around their "joint" (parent node) by a certain angle. Then after the rotations I need to get a position of a selected leaf. For simplicity: The root "joint" rotates around the x axis, all its children "joints" rotate around the y axis, their children around x, etc. So its basically like a very complicated crane, that has more rotating parts, all connected by a right angle to the previous one.

I tried to think about this problem more generally: It's basically a general tree structure, where modifying a property of a node affects all its children.

How can I create an efficient data structure for this? It would be ideal to have logarithmic complexities for rotation of subtrees and retrieving positions of leaves.

I tried to use some concepts from the usual tree data structures. My approach would be to somehow balance the tree, then retrieving the positions could be done in logarithmic time, but I have no idea how to balance a general tree without any restrictions on the number of children etc. Maybe use a different structure than just parent -> subtree as "joint" -> "affected by the joint"? Or maybe some restrictions on the tree of the "joints" structure would help?

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 subtree under given joint by its id by a given angle around its 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?