- 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 O((n+k)log(n))?
Asked By : Caio Oliveira
Answered By : Yuval Filmus
- 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 + 2epsilon$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23886 Ask a Question Download Related Notes/Documents
