FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS
Khaled Elbassioni, Amr Elmasry, Kazuhisa Makino · International Journal of Computational Geometry & Applications · 2011
We show that finding the simplices containing a fixed given point among those defined on a set of n points can be done in O(n + k) time for the two-dimensional case, and in O(n2 + k) time for the three-dimensional case, where k is the number of these simplices. As a byproduct, we give an alternative (to the algorithm in Ref. 4) O(n log r) algorithm that finds the red-blue boundary for n bichromatic points on the line, where r is the size of this boundary. Another byproduct is an O(n2 + t) algorithm that finds the intersections of line segments having two red endpoints with those having two blue endpoints defined on a set of n bichromatic points in the plane, where t is the number of these intersections.