Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: The largest Triangle that can fit in convex hull
Date: Thu, 7 May 2009 21:06:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 10
Message-ID: <gtvifq$dur$1@fred.mathworks.com>
References: <b9bb3ca1-66f4-4c5f-9553-cd970bfb7eb1@v4g2000vba.googlegroups.com> <a3eecd7c-3fb1-4f8f-ba6c-0e39057b0279@j12g2000vbl.googlegroups.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241730362 14299 172.30.248.37 (7 May 2009 21:06:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 7 May 2009 21:06:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:538360


Two observations:

- If T is a triangle that maximizes the area, we can always find a triangle with the same area where the corners are coincides with the nodes of the conver hull (since triangle area must be monotonic when corner moves along an edge).
- Given two arbitrary nodes of the convex hull where two corners of the triangles coincide with. Take this as the constraint, its is easy to find the third corner (that maximizes the area) in constant time.

So with this two observations, we can do this method: just generate a list of all the couples of nodes of the convex hull, then compute the list of respective third corner that maximizes the area, and compare the areas, take the maximum, and you are done. The complexity is O(N^2), where N is number of points in the convex hull.

Does it sound OK for you?

Bruno