Jean-Daniel Boissonnat and Franco P. Preparata. (Reporting all intersection points, generalized segments Line segment intersection)
Jump to navigation
Jump to search
Time Complexity
$O(n \log n + k \log n)$
Space Complexity
$O(n)$ words
(https://epubs.siam.org/doi/epdf/10.1137/S0097539797329373)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Real RAM, under more restrictions/considerations? (predicate arithmetic, exact arithmetic)
Year
1997