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 23:34:02 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 25
Message-ID: <gtvr5a$ll2$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> <gtvjn5$979$1@fred.mathworks.com> <gtvkuh$443$1@fred.mathworks.com> <gtvm9l$38c$1@fred.mathworks.com> <gtvo3p$2mj$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
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 1241739242 22178 172.30.248.37 (7 May 2009 23:34:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 7 May 2009 23:34:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:538387


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvo3p$2mj$1@fred.mathworks.com>...
> 
> > It sounds like you think that one of the edges of
> > the convex hull must be an edge of the maximal
> > area triangle. 
> 
> No, I don't assume such thing.
> 
> Bruno

Then there are n*(n-1)/2 pairs of vertices.

Finding the largest area triangle requires that
of the remaining vertices, you find that one
which is farthest from the edge defined by that
pair of vertices. This requires a dot product,
and a max operation. But the fact is, it will
require (n-2) such operations to find the largest
triangle given that edge asa base. This is not a
constant time operation, independent of the
number of vertices. It is an O(n) operation. So
the total computation must be O(n^3). How do
you claim to get around this?

John