Timeline for Data structure for a tree of points moving in space
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2018 at 13:14 | comment | added | D.W.♦ | @McSim, I doubt it. It's easy to see that $\log n_1 + \dots + \log n_k = O(k \log n)$. Moreover, it is possible to have $\log n_1 + \dots + \log n_k = \Omega((k \log n)/(\log k))$: consider for example the case where $n_1=\cdots=n_k=2$; then $\log n_1 + \dots + \log n_k = k$, and $\log n = \log(n_1+\dots+n_k)=\log(2k) = 1 + \log k$. | |
| Sep 26, 2018 at 9:14 | comment | added | egst | I wonder if there is any better way to express this sum of logarithms. It should a log of a product of $n_1 \cdots n_k$, where sum of $n_1 \cdots n_k$ is $n$. But I can't think of any reasonable upper boundary of this to get the $\mathcal{O}(\cdots)$ notation. | |
| Sep 26, 2018 at 7:25 | comment | added | D.W.♦ | @McSim, you're right. That was nonsense. I don't know what I was thinking. I guess the running time is $O(\log^2 n)$ rather than $O(\log n)$. Sorry about that. Thank you for catching my error. (I've updated the answer accordingly.) | |
| Sep 26, 2018 at 7:24 | history | edited | D.W.♦ | CC BY-SA 4.0 |
deleted 279 characters in body
|
| Sep 25, 2018 at 21:56 | comment | added | egst | I just got back to this problem and noticed one weird thing. Why is $\log n_1 + \cdots + \log n_k \le \log(n_1 + \cdots + n_k)$? It doesn't seem to be true. $\log_2 8 + \log_2 8 = 3 + 3 = 6 \ge 4 = \log_2(16) = \log_2(8 + 8)$ | |
| Sep 19, 2018 at 23:34 | comment | added | D.W.♦ | @McSim, yup, looks right to me! | |
| Sep 19, 2018 at 22:48 | comment | added | egst |
It's OK, it just took me a while to get to that "aha moment" :) I get it now. The index tree is actually the way to store the disjoint subpaths of a path to a particular node. So when retrieving the subpaths of let's say the node 3: I just use the nodes {1,2} and 3?
|
|
| Sep 19, 2018 at 18:30 | comment | added | D.W.♦ |
Assuming 1 is the root of the original tree and 4 the leaf, and the original tree is a path 1->2->3->4: the root of the index tree has the transformation $T_1 \circ T_2 \circ T_3 \circ T_4$ associated with it. When you rotate node 3, it changes this transformation to $T_1 \circ T_2 \circ T'_3 \circ T_4$. To retrieve the location of 1, you want the $T_1$ transformation (which can be obtained from a leaf of the index tree). To retrieve the location of 4 , use the $T_1 \circ T_2 \circ T'_3 \circ T_4$ transformation (which can be obtained from the root of the index tree).
|
|
| Sep 19, 2018 at 18:25 | comment | added | D.W.♦ | @McSim, sorry, I didn't explain that very well. Yes, that's correct, exactly as you wrote! By "consecutive subpath", I meant something like 1,2,3 or 2,3,4 or 2,3 or 3,4 or 1,2, i.e., a sequence/range/interval of consecutive nodes. (That's probably a lousy name; sorry.) | |
| Sep 19, 2018 at 10:16 | comment | added | egst |
Can you please explain, what you meant by "consecutive subpaths"? Is this understanding correct: If I have a path of 4 nodes (labeled: 1, 2, 3 and 4), the corresponding index tree would be: root = {1,2,3,4} has two children: {1,2} and {3,4}; {1,2} has children: 1 and 2; {3,4} has children: 3 and 4? Or did you mean all of the subpaths? Because that's the only way I can come up with a $log(n)$ depth for the index tree.
|
|
| Sep 18, 2018 at 22:52 | comment | added | D.W.♦ | @McSim, thanks! Glad you found it helpful. I fixed the bolding issue. | |
| Sep 18, 2018 at 22:51 | comment | added | D.W.♦ | @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)$. | |
| Sep 18, 2018 at 22:50 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 1 character in body
|
| Sep 18, 2018 at 22:29 | comment | added | egst | And just one thing, you forgot one '*' character for bold :) I cannot edit it though, as it needs at least 6 characters changed. | |
| Sep 18, 2018 at 22:18 | comment | added | egst | 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. | |
| Sep 18, 2018 at 22:08 | vote | accept | egst | ||
| Sep 18, 2018 at 22:08 | comment | added | egst | 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. | |
| Sep 18, 2018 at 21:22 | comment | added | RandomPerfectHashFunction | 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. | |
| Sep 18, 2018 at 20:39 | history | answered | D.W.♦ | CC BY-SA 4.0 |