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.

Answer 2

Actually I happened to encounter similar problem recently but the only difference was that there were around 300 pts and I solved it using bitset (C++ STL). For every pair of points, say (x[i],y[i]) and (x[j],y[j]), I formed a bitset<302>B[i][j] and B[i][j][k] stores 1 if k-th point is above line segment from point i to point j else I would store 0.

Now in a brute force manner I get three points so as to form a triangle, lets say (x[i],y[i]), (x[j],y[j]) and (x[k],y[k]), then a point,say z-th point ,would be inside triangle if B[i][j][z]==B[i][j][k] && B[j][k][z]==B[j][k][i] && B[k][i][z]==B[k][i][j] because a point inside triangle would show similar sign w.r.t. a side of triangle as the third point of triangle(one which is not on this side). So i get three bitset variables P=B[i][j], Q=B[j][k] and R=B[k][i] and there taking there bitwise AND then applying count() function to give me the active number of bits and hence the number of points within the triangle. But make sure you change variable P such that it gives B[i][j][k]=1 if not then take bitwise not (~) of this variable.

Though the above solution is problem specific, i hope it helps. This is the problem link: http://usaco.org/current/index.php?page=viewproblem&cpid=660