The number of triangles with N points inside

Question

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

Answer 1

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

Thus, the number of points in ABC will be the number of intersection points of L (AB), L (AC) and L (BC). (Instead, you can consider R (AB) depending on the orientation of the triangle).

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

Then we check all the triangles and find the intersections of the three sets. If we use a hash table structure for sets, then finding intersection points is like a hash table. 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 search in L (AC) and L (BC) so that there is a maximum of 2n searches in the hash table.

You might find it easier to look at the geometric search table. Divide your entire domain into a coarse grid, say, a 10 by 10 grid. Then we can put each point in the set G (i, j). Then we can split the sets L (AB) into each grid cell. Let's say we call these sets L (AB, i, j) and R (AB, i, j). When testing for intersections, the first training session, the grid cells of which lie at the intersection. This greatly reduces the search space, and since each set L (AB, i, j) contains fewer members, there will be fewer hash table queries.

Answer 2

In fact, I recently had to face a similar problem, but the only difference was that there were about 300 points, and I decided to use it with a bitset (C ++ STL). For each pair of points, say (x [i], y [i]) and (x [j], y [j]), I formed a bit set <302> B [i] [j] and B [i] [j] [k] stores 1 if the k-th point is above the line segment from point i to point j, otherwise I would save 0.

Now in brute force I get three points to form a triangle, say (x [i], y [i]), (x [j], y [j]) and (x [k], y [k]) then the point, for example the z-th point, will be inside the 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 the point inside the triangle will show the same wrt side of the triangle as the third point triangle (one of which is not on this side). Thus, I get three bit variables P = B [i] [j], Q = B [j] [k] and R = B [k] [i] and there is bitwise And then using the count () function to give me the active number of bits and therefore the number of points in the triangle. But make sure that you change the variable P so that it produces B [i] [j] [k] = 1, if not then take the bitwise (~) of this variable.

Although the above solution is specific to a specific task, I hope this helps. This is the problem: http://usaco.org/current/index.php?page=viewproblem&cpid=660