I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding leaves on the tree (i.e. sum of edge weights of the path connecting the leaves), and then $u$, $v$ must satisfy at least one of the following condition:

  • $|u_x-v_x|\ge d_{uv}$, or
  • $|u_y-v_y|\ge d_{uv}$;

otherwise, the two points are considered collided.

I'm looking for an efficient online-algorithm for finding all collisions, given the edge-weighted tree and the coordinates of the points. By online I mean all inputs could change over time.

In the special case where the tree is a star, this problem can be reduced to the traditional rectilinear rectangle collision detection, and a $O(n \log n)$ algorithm exists, say for example using a quadtree. But I don't quite see how a similar technique can be applied to general trees in my problem.

I'm also familiar with algorithms that can quickly return the distance of two nodes on the tree (say by using LCA), but to solve my problem I still need a lot more than that.

I've been struggled with this for too long, please help! Thanks so much.

  • $\begingroup$ How would you proceed if you could efficiently iterate the nodes in ascending order of one of the ordinates? $\endgroup$
    – greybeard
    Jun 27 at 7:57
  • $\begingroup$ @greybeard OK, let's say we're in 1D situation and I already have the points sorted by their location, and also assume that I can lookup the tree-distance of any pair of leaves in O(1) time. In order to do better than O(n^2), where n is the number of leaves/points, I suppose I would need to somehow avoid checking pairs of points that obviously would not collide. My problems is that I don't see how. A pair of points could be very far apart in location, when their corresponding tree-distance is even greater. More hint is needed please. $\endgroup$ Jun 27 at 11:34
  • $\begingroup$ Well, maximum distance has the advantage of being a norm: you possibly can take advantage of the triangle inequality. $\endgroup$
    – greybeard
    Jun 27 at 13:50
  • $\begingroup$ @greybeard Yes, I did realize later from your mentioning of sorting that, supposing that points $a,b,c$ are in order, $a$ does not collide with $b$ and $b$ does not collide with $c$, then it is easy to show that $a$ also does not collide with $c$. So after sorting and checking all pairs of points that are adjacent (in order), indeed there'll only be a few left that still needs to be checked in most cases. On average I think this could give me an algorithm that is $O(n \log n + k)$ where $k$ is the number of collisions, although I still need to think about how to implement it. $\endgroup$ Jun 27 at 22:54
  • $\begingroup$ @D.W. I need this algorithm for my own project (the stipulation has been simplified for clarity), in which the app needs to respond quickly if the user creates a collision by dragging the components. I wasn't too sure if it can be made more efficient, but now I'm more certain from the idea given above. See star and Q-tree. $\endgroup$ Jun 27 at 23:00

Your Answer

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

Browse other questions tagged or ask your own question.