The largest triangle of many points

Question

Possible duplicate:
How to find the largest triangle in a convex hull aside from brute force search

I have a set of random points from which I want to find the largest triangle in the region, each of which has verticals at one of these points.

So far, I have figured out that the largest triangular triangles will only lie on the outer points of a point cloud (or convex hull), so I programmed a function to do just that (using Graham scan at nlogn time).

However, where I am stuck. The only way to figure out how to find the largest triangle of these points is to use brute force n ^ 3 times, which is still acceptable in the middle case, since the convex hull algorithm usually yields a huge number of points. However, in the worst case, when the points are on a circle, this method fails.

Does anyone know the algorithm longer to do this more efficiently?

Note. I know that CGAL has this algorithm, but they do not go into details about how this is done. I don’t want to use libraries, I want to study this and program it myself (and also let me configure it the way I want it to work, just like a graham scan in which other implementations collect collinear points that I don’t want).

Answer 1

I don’t know if this help will help, but if you select two points from the convex hull and rotate all the points of the shell so that the connecting line of the two points is parallel to the x axis, either the point with maximum or the one with the minimum y coordinate forming the triangle with the largest area along with two selected points.

Of course, once you have tested one point for all possible baselines, you can remove it from the list.

Answer 2

On top of my head, maybe you could do something related to a grid or splitting a collection of glasses into groups? Perhaps ... dividing the points into three groups (not sure if the best way to do this in this case, though) is to do something to drop these points in each group, which are closer to two different groups than the other points in of the same group and then using the remaining points to find the largest triangle that can be made with one vertex in each group? This would actually make the case where all the points on the circle much easier, because you would just focus on the points that are near the center of the arcs contained in each group, since they would be in each group farthest from the two other groups.

I'm not sure if this will give you the correct result for certain triangles / point distributions. There may be situations when the resulting triangle does not have an optimal area, because the choice of group and / or vertices are not / not optimal. Something like that.

In any case, these are my thoughts on this issue. Hopefully, at least I was able to give you ideas on how to work on this.

Answer 3

Here's a thought on how to get it to O (n ² log n). I don't know anything about computational geometry, so I will mark this community wiki; Please feel free to improve this.

Pre-process the convex hull by finding for each point the range of slope of the lines through this point, so that the set lies completely on one side of the line. Then invert this relation: build a spacing tree for slopes with points in the leaf nodes, so when prompted with a slope, you will find points such that there is a tangent through these points.

If there are no sets of three or more collinear points on the convex hull, for each slope (two on each side) there should be no more than four points, but in the case of collinear points we can simply ignore the intermediate points.

Now iterate over all pairs of points (P, Q) on the convex hull. We want to find the point R so that the triangle PQR has a maximum area. Taking PQ as the base of the triangle, we want to maximize the height by finding R as far as possible from the PQ line. The line through R parallel to PQ must be such that all points lie on one side of the line, so we can find a limited number of candidates in O (log n) time using a tree with a pre-built interval.

To improve this in practice, branch and snap in a set of pairs of points: find the upper boundary of the height of any triangle (for example, the maximum distance between two points) and discard any pair of points that is multiplied by this upper boundary less than the largest triangle found.

Answer 4

I think that the method of rotating calipers can be applied here.

Answer 5

How about lowering a point at a time from a convex hull? Starting with the convex hull, calculate the area of ​​the triangle formed by each triple of neighboring points (p1p2p3, p2p3p4, etc.). Find the triangle with the smallest area, then lower the middle of the three points that make up this triangle. (In other words, if the region's minimum triangle is p3p4p5, leave P4.) Now you have a convex polygon with N-1 points. Repeat the same procedure until you are left with three dots. This should take O time (N ^ 2).

I would not be surprised if there is any pathological case when this does not work, but I expect it to work in most cases. (In other words, I have not proved this, and I have no source for quoting.)