Finding Intersections of Bichromatic Segments Defined by Points.
Amr Elmasry, Kazuhisa Makino · 2007
Consider a set of n points in ℜ², each colored either red or blue. A line segment defined by two red points is a red segment, and that defined by two blue points is a blue segment. A bichromatic intersection is an intersection between a red segment and a blue segment. We give an O(n 2 + k) algorithm that reports k bichromatic intersections defined by the n points. Extending our algorithm to points on spherical curves, we can report in O(n 2 + k) time the k simplices, defined by n points in ℜ 3, containing a specified point in their interior.