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 22:11:01 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 38
Message-ID: <gtvm9l$38c$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>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241734261 3340 172.30.248.35 (7 May 2009 22:11:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 7 May 2009 22:11:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:538373


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvkuh$443$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gtvjn5$979$1@fred.mathworks.com>...
> 
> > 
> > I'll claim that this is an O(N^3) operation, as
> > pointed out in my response.
> > 
> 
> John, I'll claim that by book keeping correctly the couple of vertexes, the third one can be found in constant time (no need to go the full round the hull to find it). Think like a basic move of simplex method. ;-)
> 
> Do I miss something?

I don't see it. I'll claim that for any pair of vertices
in the hull, you must check each of the other N-2
vertices. (Actually, not quite, since you can exclude
the triangles you have already seen. In essence, you
must check all nchoosek(N,3) possible triangles. The
nice thing is nchoosek gives you the complete list
of triangles to check.

This is simple to do in a vectorized operation, as I
showed, but it is still O(N^3) in the size of the
convex hull.

It sounds like you think that one of the edges of
the convex hull must be an edge of the maximal
area triangle. As it turns out, the example I ran
in my response did not have that happen. The
maximal area triangle that was found had a
considerably larger area than if I had only looked
at triangles with an edge that was conincident
with an edge of the convex hull.

The maximal area was 7.5423, yet by looking
only at those triangles which shared an edge
of the convex hull, 4.7898 was the maximal area.

John