Triangle enclosing the biggest number of points

Question

Given set of 2D points find a triangle built from those points, that encloses the biggest number of points.

Brutal algorithm for this is just building triangles from every possible triad of points and checking how many points they enclose, but time complexity of this solution is O(n^4).

For the optimal solution I thought about first finding the convex hull of those points and arranging points inside this hull with some structure, but I can't figure it out.

Do you have any ideas about the optimal solution for this kind of problem?

Answer 1

In a set of n points, there are (n choose 3) triangles, and using brute force to check for each point whether it is contained in each triangle indeed has O(n⁴) complexity. To give a practical example of a few set sizes:

points:            100              1,000                   10,000
triangles:     161,700        166,167,000          166,616,670,000
checks:     15,684,900    165,668,499,000    1,665,666,849,990,000

Below are a few geometrical ideas; they don't lead straight to a solution, but they can reduce the number of triangles that have to be checked.

Counter-example for convex hull

First of all, using only points on the convex hull is not guaranteed to give the optimal solution. Consider this counter-example:

The convex hull is the red rectangle. However, if we use two of its sides and a diagonal to form a triangle, the diagonal will cut through the central point cluster and leave out some of the points. And even if we only use 1 or 2 corners of the rectangle, combined with a point in the center, it will always cut through the blue triangle and leave out some points. The blue triangle, which has no points on the convex hull, is in fact the optimal solution.

Triangle contained in triangle

If you consider a triangle abc, and three points d, e and f contained within it, then the triangle def cannot be the triangle which contains the most points, because triangle abc contains at least three more points. Triangles made from a combination of points from abc and def, like abd, also contain fewer points than abc.

This means that finding a triangle and some points contained within it, allows you to discard a number of triangles. In the next paragraphs, we will use this idea to discard as many triangles as possible from having to be checked.

Expanding a triangle

If we consider a triangle made from three randomly chosen points a, b and c (named clock-wise), and then check whether all other points are on the left of right side of the lines |ab|, |bc| and |ca|, the points are partitioned into 7 zones:

If we replace a corner point of the triangle by a point in the adjacent coloured zone, e.g. zone LRL for point a, we get a larger triangle that contains triangle abc. If we randomly pick three points from zones LRL, LLR and RLL, we can expand the triangle like this:

We can then partition the points again using this new triangle a'b'c' (points already in zone RRR can be added to the new zone RRR without checking) and expand the triangle again as long as there is at least one point in the zones LRL, LLR or RLL.

If we have caught enough points inside the expanded triangle, we can now use the brute force algorithm, but skip any triangle which doesn't have a point outside of the expanded triangle a'b"c'.

If we haven't caught enough points to make that feasible, we can try again with another three random points. Note, however, that you should not use the union of the points contained within several triangles; three points which are each contained in another triangle, but not in the same triangle, can still be the triangle containing the most points.

Excluding triangles in multiple steps

We could repeatedly choose a random triangle, expand it maximally, and then mark the triangles made from three points on or inside the triangle, to then exclude these from the check. This would require storing a boolean for all possible triangles, e.g. in a 3D bit array, so it is only feasible for sets up to a few thousand points.

To simplify things, instead of expanding random triangles, we could do this with a number of randomly chosen triangles, or triangles made from points on the convex hull, or points far apart when sorted in the x or y-direction, or ... But any of these methods will only help us to find triangles which can be excluded, they will not give us optimal (or even good-enough) triangles by themselves.