# Collision detection with vary constraints

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.

• @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. Jun 27 at 22:54