Number of triangles with N points inside

Question

Given some points in plane (upto 500 points), no 3 collinear. We have to determine the number of triangles whose vertices are from the given points and that contain exactly N points inside them. How to efficiently solve this problem? The naive O(n^4) algorithm is too slow. Any better approach?

Answer 1

You could try thinking of the triangle as the intersection of three half-spaces. To find the number of points inside a triangle A, B, C first consider the set of points on one side of the infinite line in direction AB. Let these sets L(AB) and R(AB) for points of the left and right. Similarly you the same with other two edges and build sets L(AC) and R(AC) and sets L(BC) and R(BC).

So the number of points in ABC will be the number of points in the intersection of L(AB), L(AC) and L(BC). (You might want to consider R(AB) instead depending on the orientation of the triangle).

Now if we want to consider the full set of 500 points. First take all pairs of points AB and construct the sets L(AB) and R(AB). This will take O(n^3) operations.

Next we test all triangles and find the intersections of the three sets. If we use some hash table structure for the sets then to find the intersection points is like a hashtable lookups. If L(AB) has l elements, L(AC) has m elements and L(BC) n elements. Say l > m > n. For each point in L(BC) we need to do a lookup in L(AC) and L(BC) so thats a maximum of 2n hashtable lookups.

It might be faster to consider a geometric lookup table. Divide your whole domain into a coarse grid say a 10 by 10 grid. We can then put each point into a set G(i,j). We can then split the sets L(AB) into each grid cell. Say call these sets L(AB,i,j) and R(AB,i,j). In testing for intersections first workout which grid cells lie in the intersection. This dramatically reduces the search space and as each set L(AB,i,j) contain fewer members there will be fewer hashtable lookups.