MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi
Learn moreOpportunities for recent engineering grads.
Apply TodayMATLAB Central > MATLAB Newsreader > The largest Triangle that can fit in convex hull 

Subject: The largest Triangle that can fit in convex hull From: Dodo Date: 4 May, 2009 17:37:54 Message: 1 of 26 
Hi 
Subject: The largest Triangle that can fit in convex hull From: Damian Sheehy Date: 4 May, 2009 18:18:30 Message: 2 of 26 
Before anyone can attempt to answer that question, you have to define what 
Subject: The largest Triangle that can fit in convex hull From: Dodo Date: 7 May, 2009 20:42:19 Message: 3 of 26 
On May 4, 9:18 pm, "Damian Sheehy" <Damian.She...@mathworks.com> 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 7 May, 2009 21:06:02 Message: 4 of 26 
Two observations: 
Subject: The largest Triangle that can fit in convex hull From: John D'Errico Date: 7 May, 2009 21:25:03 Message: 5 of 26 
Dodo <lovelygirl_2220@hotmail.com> wrote in message <a3eecd7c3fb14f8fba6c0e39057b0279@j12g2000vbl.googlegroups.com>... 
Subject: The largest Triangle that can fit in convex hull From: John D'Errico Date: 7 May, 2009 21:27:01 Message: 6 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvifq$dur$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 7 May, 2009 21:48:01 Message: 7 of 26 
"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gtvjn5$979$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: John D'Errico Date: 7 May, 2009 22:11:01 Message: 8 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvkuh$443$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Matt Date: 7 May, 2009 22:32:01 Message: 9 of 26 
Dodo <lovelygirl_2220@hotmail.com> wrote in message <b9bb3ca166f44c5f9553cd970bfb7eb1@v4g2000vba.googlegroups.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 7 May, 2009 22:42:02 Message: 10 of 26 

Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 7 May, 2009 22:46:02 Message: 11 of 26 
"Matt " <xys@whatever.com> 
Subject: The largest Triangle that can fit in convex hull From: Matt Date: 7 May, 2009 23:02:03 Message: 12 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvoba$hrd$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: John D'Errico Date: 7 May, 2009 23:34:02 Message: 13 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvo3p$2mj$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 00:06:02 Message: 14 of 26 
> The most general definition of a convex hull of a region S is the smallest convex region enclosing S. In particular, the convex hull need not be polyhedral and need not have vertices, e.g. the convex hull of an ellipse, or some more complicated curve. 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 00:08:01 Message: 15 of 26 
> How do 
Subject: The largest Triangle that can fit in convex hull From: Matt Date: 8 May, 2009 01:53:01 Message: 16 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvt1a$leg$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 07:01:02 Message: 17 of 26 
"Matt " <xys@whatever.com> wrote in message <gu039t$m0c$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 09:15:03 Message: 18 of 26 
I have cleaned up my code. I have performed few experimental runs to check the time follows O(N^2) law. It looks like it is. Though it's quite long: for 1000 vertexes, it takes about 4 full minutes, where as for hull of Gaussian random data points, a few mini seconds maximum is needed because the hull has very few vertexes (#20). 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 10:37:01 Message: 19 of 26 
I have optimized the code using profiler, put it in a mfile function and now it takes about 18s for 1000 vertexes points. ;) 
Subject: The largest Triangle that can fit in convex hull From: Matt Date: 8 May, 2009 12:25:03 Message: 20 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gu0lbe$g1v$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Matt Date: 8 May, 2009 14:35:01 Message: 21 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gu0lbe$g1v$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 8 May, 2009 18:41:01 Message: 22 of 26 
My code now runs about 12.5s for 1000 points; and 50s for 2000 points. ;) 
Subject: The largest Triangle that can fit in convex hull From: lovelygirl2220@gmail.com Date: 10 May, 2009 19:28:31 Message: 23 of 26 
On May 8, 9:41 pm, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote: 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 10 May, 2009 20:06:01 Message: 24 of 26 
lovelygirl2220@gmail.com wrote in message <fd9acebb328246499c709df0076bbc6e@v4g2000vba.googlegroups.com>... 
Subject: The largest Triangle that can fit in convex hull From: avd122 daga Date: 9 Jul, 2009 15:08:02 Message: 25 of 26 
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvifq$dur$1@fred.mathworks.com>... 
Subject: The largest Triangle that can fit in convex hull From: Bruno Luong Date: 9 Jul, 2009 18:28:02 Message: 26 of 26 
Let T is the maximized triangle, AB is the base of T. C is the opposite triangle corner. C belongs to the convexhull. If C is on the edge of the hull, then the edge must be parallel to AB (otherwise the derivative of the area of T with respect to C is not zero). So I can move C to one of the corner of the hull edge, and the area of the triangle remains unchanged. So I can select C is a corner. Thus I can select A, B, and C. 
A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.
Anyone can tag a thread. Tags are public and visible to everyone.