11

Possible Duplicate:
How to find largest triangle in convex hull aside from brute force search

I have a set of random points from which i want to find the largest triangle by area who's verticies are each on one of those points.

So far I have figured out that the largest triangle's verticies will only lie on the outside points of the cloud of points (or the convex hull) so i have programmed a function to do just that (using Graham scan in nlogn time).

However that's where I'm stuck. The only way I can figure out how to find the largest triangle from these points is to use brute force at n^3 time which is still acceptable in an average case as the convex hull algorithm usually kicks out the vast majority of points. However in a worst case scenario where points are on a circle, this method would fail miserably.

Dose anyone know an algorithm to do this more efficiently?

Note: I know that CGAL has this algorithm there but they do not go into any details on how its done. I don't want to use libraries, i want to learn this and program it myself (and also allow me to tweak it to exactly the way i want it to operate, just like the graham scan in which other implementations pick up collinear points that i don't want).

Community
  • 1
  • 1
Faken
  • 11,352
  • 17
  • 59
  • 74
  • What's the name of the routine in CGAL that does this? – andand Jun 17 '10 at 20:25
  • @andand: maximum_area_inscribed_k_gon_2, i think. – Faken Jun 17 '10 at 20:27
  • @Faken: The source code doesn't say what algorithm CGAL::maximum_area_inscribed_k_gon_2 uses. Still, you might want to take a look at it (http://www.cgal.org/Manual/latest/include/CGAL/extremal_polygon_2.h) and see if you can reconstruct the logic. – andand Jun 17 '10 at 20:36
  • @andand: Well, I'm a mechanical engineer by training so looking at a pro programmer's code is like translating french...either way, thanks for the starting point, I'll see what i can make of it. – Faken Jun 17 '10 at 20:40
  • @Faken: I haven't taken a really good look at it the CGAL approach, but it appears to be recursive. I doubt they'd incur the overhead if they couldn't get at least O(N log N) performance out of it. I'll look at it some more and see if I can figure it out. – andand Jun 17 '10 at 21:28
  • 6
    @Faken: This is an exact duplicate of http://stackoverflow.com/questions/1621364/how-to-find-largest-triangle-in-convex-hull-aside-from-brute-force-search. The accepted answer provides well stated O(n) solution. – andand Jun 18 '10 at 02:50
  • 1
    @andand: A method simmilar to that had crossed my mind but I disregarded it pretty quickly as I couldn't prove that it would always end up with the largest triangle (and worse, i had thought that i had a counter example to it as well, which i neglected to actually test on paper). The idea is extremely simple, thanks for pointing it out to me, gives me another avenue to explore, though to be honest, i still have my doubts, O(n) time? sounds too good to be true. – Faken Jun 19 '10 at 06:11
  • @Faken: It is O(n) _after_ computing convex hull, so it is O(nlogn) in your case. –  Jun 20 '10 at 02:14
  • I already have a convex hull, I wanted something that was better than n^3 time on the hull points so it really is in O(n) time. Though, I'm at a loss on how to close this question, i have an answer but its not a posted answer. – Faken Jun 20 '10 at 21:27
  • @Faken: If you want it closed, you can flag it for mod attention I suppose. Or just wait for some more users to come and close it. It already has 2 votes (one of which is mine). Your question is essentially same as the other question (which has an answer) and this question needs to be closed as a dupe of that. –  Jun 21 '10 at 17:49
  • @faken or answer it yourself. – bmargulies Jun 24 '10 at 11:36

5 Answers5

1

Don't know if this help, but if you choose two points from the convex hull and rotate all points of the hull so that the connecting line of the two points is parallel to the x-Axis, either the point with the maximum or the one with the minimum y-coordinate forms the triangle with the largest area together with the two points chosen first.

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

Landei
  • 54,104
  • 13
  • 100
  • 195
0

Off the top of my head, perhaps you could do something involving gridding/splitting the collection of points up into groups? Maybe... separating the points into three groups (not sure what the best way to do that in this case would be, though), doing something to discard those points in each group that are closer to the other two groups than other points in the same group, and then using the remaining points to find the largest triangle that can be made having one vertex in each group? This would actually make the case of all points being on a circle a lot simpler, because you'd just focus on the points that are near the center of the arcs contained within each group, as those would be the ones in each group furthest from the other two groups.

I'm not sure if this would give you the proper result for certain triangles/distributions of points, though. There may be situations where the resultant triangle isn't of optimal area, either because the grouping and/or the vertex choosing aren't/isn't optimal. Something like that.

Anyway, those are my thoughts on the problem. I hope I've at least been able to give you ideas for how to work on it.

JAB
  • 20,783
  • 6
  • 71
  • 80
0

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

Preprocess the convex hull by finding for each point the range of slopes of lines through that point such that the set lies completely on one side of the line. Then invert this relationship: construct an interval tree for slopes with points in leaf nodes, such that when querying with a slope you find the points such that there is a tangent through those points.

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

Now, iterate through all pairs of points (P,Q) on the convex hull. We want to find the point R such that triangle PQR has maximum area. Taking PQ as the base of the triangle, we want to maximize the height by finding R as far away from the line PQ as possible. 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 bounded number of candidates in time O(log n) using the preconstructed interval tree.

To improve this further in practice, do branch-and-bound in the set of pairs of points: find an upper bound for the height of any triangle (e.g. the maximum distance between two points), and discard any pair of points whose distance multiplied by this upper bound is less than the largest triangle found so far.

Jouni K. Seppänen
  • 43,139
  • 5
  • 71
  • 100
  • "I don't really know anything about computational geometry, so I'll mark it community wiki[.]" Being in the same boat, I suppose I'll mark mine CW as well. – JAB Jun 17 '10 at 20:56
  • I don't know why you marked it as a community wiki, anything helpful could be considered as a base for an actual answer. – Faken Jun 17 '10 at 21:00
0

I think the rotating calipers method may apply here.

lhf
  • 70,581
  • 9
  • 108
  • 149
  • I encountered this during my research but only at a glance. At first glance, i don't quite understand how this might work, what is your line of thinking on this? – Faken Jun 17 '10 at 21:01
  • Use the same algorithm that computes the diameter: for each convex hull edge, the point farthest from it defines the largest triangle with that edge as base. Rotate once and find the largest triangle overall. But that's not a proof... – lhf Jun 17 '10 at 21:10
  • So it would compute in n^2 time. Significant improvement. Unfortunately there's no guarantee that the largest triangle would have an edge on the hull. Take 6 points that form a perfect hexagon for example. – Faken Jun 17 '10 at 21:22
-1

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

I would not be at all surprised if there is some pathological case where this doesn't work, but I expect that it would work for the majority of cases. (In other words, I haven't proven this, and I have no source to cite.)

John
  • 267
  • 1
  • 3
  • Hmm, no I don't think that's correct. Consider a perfect hexagon. We know the largest triangle in there would be a triangle connecting every other point. The algorithm described would first start by removing a point (doesn't matter which point, they are all the same). we are left with 5 points. If the algorithm removes the next point two points to the left or right of the point removed, it would yield the correct answer. However if it removed the point opposite of the point removed, it would yield a wrong answer. Good try though, gets me thinking. – Faken Jun 17 '10 at 21:16