Nearest neighbour search in a constantly changing set of line segments

Question

I have a set of line segments. I want to perform the following operations on them:

1. Insert a new line segment.
2. Find all line segments within radius R of a given point.
3. Find all points within radium R1 of a given point.
4. Given a line segment, find if it intersects any of the existing line segments. Exact intersection point is not necessary(though that probably doesnt simplify anything.)

The problem is algorithms like kd/bd tree or BSP trees is that they assume a static set of points, and in my case the points will constantly get augmented with new points, necessitating rebuilding the tree.

What data-structure/algorithms will be most suited for this situation ?

Edit: Accepted the answer that is the simplest and solves my problem. Thanks everyone!

Answer 1

One possibility is dividing your space into a grid of boxes - perhaps 10 in the y-axis and 10 in the x-axis for a total of 100.

Store these boxes in an array, so it's very easy/fast to determine neighboring boxes. Each box will hold a list vector of line segments that live in that box.

When you calculate line segments within R of one segment, you can check only the relevant neighboring boxes.

Of course, you can create multiple maps of differing granularities, maybe 100 by 100 smaller boxes. Simply consider space vs time and maintenance trade-offs in your design.

• updating segment positions is cheap: just integer-divide by box sizes in the x and y directions. For example, if box-size is 20 in both directions and your new coordinate is 145,30. 145/20==7 and 30/20==1, so it goes into box(7,1), for a 0-based system.