How to find triangles with maximum area?

Question

Algorithms

Problem: You are given 3n points on a plane, and no three of them lie on the same line. Construct a set of n triangles with vertices at these points so that no two triangles intersect and contain each other, and the total area of ​​these triangles is maximum.
I'm trying to find the right approach to the problem.
I started solving head-on: first, I go through all the points and write all possible triangles into a two-dimensional array.
That is, if 6 points are given, then the beginning of the array will look like this: [[0,1,2], [0,1,3], [0,1,4], [0,1,5], [0, 2,3], [0,2,4], etc., where the numbers in the array are the indices of the points we know. For 6 points, 20 different triangles are obtained. For 9 points - 84 triangles, etc.
Next, as I understand it, you need to compare each triangle with each in order to identify which 2 triangles (in the case of 6 points) have the largest area and do not intersect. I implement this using a recursive function and it turns out that for 20 triangles there will be 190 iterations (combinatorics, combinations of twenty by two).
But the problem is that if there are 9 points, then there will be 84 possible triangles and already 95284 iterations (84 by 3) and for 12 points there will be 220 triangles and 94.966.795 iterations (220 by 4). And the program will not count 15 points at all in adequate time.
And the problem is that the program should not crash already at 15 points.
I understand that this approach is apparently wrong, but no other solution has yet come to mind
I do not throw the code, because I ask you to suggest exactly the approach to the task

Answer 1

Up to 15 points can be done by exhaustive search. You need to enumerate all partitions of 3n points into triples. There are (3n)!/(3!)^n/n! for n=5, that's a little over a million.
You sort through all the triangles, even if they have common points, this greatly inflates the number of options.
You can sort through recursively - take the first point without a triangle and sort out the 2 remaining ones, which will form a triangle with it. Triangle them and recursively run further. Then roll back the last changes and sort through other options. Next, you need to check that no 2 triangles intersect and do not lie in each other. If this is also done as it is generated, then it is possible to speed up the solution quite well by cutting off obviously impossible options. Maybe even up to 21 single points will work tolerably in terms of speed.
Some geometric solution does not come to mind.

Answer 2

This is a classic problem and an old well-known solution - Delaunay triangulation
https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B8%D...

Answer 3

Well, here, obviously, you first need to define some kind of bounding rectangle and then recursively break it into smaller ones and process its parts.