Timeline for Data structure for a tree of points moving in space
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2018 at 22:26 | comment | added | egst | And yes, no balancing can be done on the original tree, but maybe storing the information in a different tree structure, that would convey the same information, but may be balanced? Something like the @D.W.'s answer. But I understand, that the dynamic case coud need a completely different approach. | |
| Sep 18, 2018 at 22:23 | comment | added | egst | 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. | |
| Sep 18, 2018 at 22:12 | comment | added | egst | 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. | |
| Sep 18, 2018 at 22:01 | comment | added | RandomPerfectHashFunction | @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. | |
| Sep 18, 2018 at 21:24 | history | edited | RandomPerfectHashFunction | CC BY-SA 4.0 |
added 20 characters in body; edited body
|
| Sep 18, 2018 at 21:11 | history | edited | RandomPerfectHashFunction | CC BY-SA 4.0 |
deleted 13 characters in body
|
| Sep 18, 2018 at 20:59 | comment | added | RandomPerfectHashFunction | @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. | |
| Sep 18, 2018 at 20:48 | comment | added | D.W.♦ | 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.) | |
| Sep 18, 2018 at 20:44 | history | answered | RandomPerfectHashFunction | CC BY-SA 4.0 |