3
$\begingroup$

So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, at the beginning of every timestep, that no intersections exist within the set of all line segments that constitute the surface, and at every timestep, a fixed number of nodes is altered (if this produces intersections, the simulation resets). Let's call the set of all lines after an alteration N and the lines that have been altered K. I then know that I should only look for intersections within K and between K and {N - K}, because I know there can be no intersections within {N - K}. This is equivalent to wanting to find intersections between K and N.

When I first tackled this problem, I just implemented sweepline, but now I realize that it finds intersections within a set. As far as I can tell, adapting the algorithm to find intersections between segments in a set X and segments in a set Y is quite tricky; I haven't been able to work that out. The only things I thought of is doing brute force (which amounts to |K| * |N|) and just ignoring K and applying sweepline, which is |N|lg|N|. If there's a way to combine the best of both approaches,I'd expect there to be a big difference in the performance of my code. Is there such a way?

$\endgroup$
  • 1
    $\begingroup$ So, in short, you ask whether the knowledge that you have only intersections between set K and N, with K small, instead of intersections on one set X gives an advantage. I think you should trim your post a bit, because it contains quite a bit of information unnecessary for answering the question. (I don't think the application for finding intersections is important for answering your question, but do explain if it is) Also, the title doesn't seem to correspond to your actual question, you might want to change it. $\endgroup$ – Discrete lizard Apr 15 '18 at 16:40
  • $\begingroup$ @Discretelizard thanks for the feedback. I thought briefly explaining what the application was could provide someone with insight into a potentially totally different direction to take. I'll make the appropriate changes. $\endgroup$ – André Muricy Apr 15 '18 at 17:01
3
$\begingroup$

The problem you describe is known as the red-blue intersection problem. Here, we have a red set of $n_1$ segments and a blue set of $n_2$ segments and we know that there are only intersections between segments of different colour. Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n_1+n_2$ is still optimal1 when if we have no further information.

In particular, we cannot easily combine the two approaches. To get some intuition on why adapting the sweepline algorithm in particular doesn't simply work, consider the case where $n_1=1$ and $n_2 = 1000$ and take a large blue segment such that the rectangle that has this segment as a diagonal contains all endpoints of the red segments. In this case, all red segments could be intersecting the single blue segment, so the sweepline has to consider all points in $n_2$ as event points and hence it is possible we have to spend at least $\Omega(n_2\log n_2)$ time on our sweepline algorithm.


There is one special case in which we can be faster. A planar subdivision is simply connected when each closed path over the edges within the same region of a subdivision can be topologically contracted to a point, i.e. a region cannot contain another region (similar to a simply connected space). If the two sets of segments form two simply connected planar subdivisions, we can use the algorithm by U. Finke and K. Hinrichs. to find all intersections in $O(n+k)$ time.

1. Optimal if $n_1\approx n_2$. Of course, if $n_2 \ll\log n_1$, we can do better with the naive algorithm, but that is rarely the case.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.