Bichromatic Line Segment Intersection Counting in O(n sqrt(log n)) Time.
Timothy M. Chan, Bryan T. Wilkinson · 2011
We give an algorithm for bichromatic line segment intersection counting that runs in O(n p logn) time under the word RAM model via a reduction to dynamic predecessor search, oine point location, and oine dynamic ranking. This algorithm is the rst to solve bichromatic line segment intersection counting in o(n logn) time.