4
$\begingroup$

I'm looking for a sweep line algorithm for finding all intersections in a set of line segments which doesn't necessarily require the general position constraint of Bentley-Ottman's algorithm (taken from Wikipedia):

  • No two line segment endpoints or crossings have the same x-coordinate
  • No line segment endpoint lies upon another line segment
  • No three line segments intersect at a single point.

Is there any sweep line solution to this problem? If not, is there any other algorithm that solves this problem in $\mathcal{O}((n+k) \log(n))$?

Improve this question
$\endgroup$
2
$\begingroup$

Usually these algorithms can be adapted to the general case, but the details are messy and hard to get right. Another option is perturbation:

  • Move each line segment by some small amount in all directions.
  • Extend the segments slightly on both ends.

If you choose your parameters carefully (i.e., small enough), you are likely to have all the same intersections, but you will be in general position with probability 1. How small is small depends on your input, and this is a limitation of this approach, but in practice you can probably heuristically choose a small enough perturbation.

Implementing this using "virtual infinitesimals", you can come up with a version of Bentley–Ottman that doesn't require general position. The idea is to do the perturbation by some infinitesimal amount, and record the results formally (e.g. $1$ goes to $1+\epsilon$, where $\epsilon$ is an infinitesimal). When running the algorithm, you will need to compare values which involve these infinitesimals, which you can do formally (for example, $1+\epsilon < 1 + 2\epsilon$).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I've read about using perturbation in Bentley-Ottman, but I couldn't understand how to do it properly. For example, I need to add a perturbation to a line segment so that it does not cross with other line segment at the same point it crosses a third line segment: how do I choose this perturbation? What guaranties do I have that this perturbation will make the Bentley-Ottman algorithm work? $\endgroup$ – Caio Oliveira Apr 17 '14 at 21:14
  • $\begingroup$ To clarify, I had this specific doubt when I read this problem: uva.onlinejudge.org/… I've read that it can be solved using something called cicle sweep, but as there will be at most 10^5 +10^4 line segments (counting all seek and hidden children as the endpoints of line segments), another O(n log(n)) algorithm to check intersections should do too. $\endgroup$ – Caio Oliveira Apr 17 '14 at 21:18
  • 1
    $\begingroup$ @Caio Oliveira You can either add a random perturbation, or add an infinitesimal perturbation which makes all endpoint coordinates distinct. $\endgroup$ – Yuval Filmus Apr 17 '14 at 22:34
  • $\begingroup$ I understand that in theory this works, but how can I implement it? Floating point errors will arise by using this technique and eventually generate a wrong answer (not finding an intersection, for example). $\endgroup$ – Caio Oliveira May 4 '14 at 14:20

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.