Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: The largest Triangle that can fit in convex hull
Date: Thu, 7 May 2009 21:27:01 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 16
Message-ID: <gtvjn5$979$1@fred.mathworks.com>
References: <b9bb3ca1-66f4-4c5f-9553-cd970bfb7eb1@v4g2000vba.googlegroups.com> <a3eecd7c-3fb1-4f8f-ba6c-0e39057b0279@j12g2000vbl.googlegroups.com> <gtvifq$dur$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241731621 9449 172.30.248.38 (7 May 2009 21:27:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 7 May 2009 21:27:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:538364


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvifq$dur$1@fred.mathworks.com>...
> 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

I'll claim that this is an O(N^3) operation, as
pointed out in my response.

John