Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: The largest Triangle that can fit in convex hull
Date: Fri, 8 May 2009 01:53:01 +0000 (UTC)
Organization: Xoran Technologies
Lines: 9
Message-ID: <gu039t$m0c$1@fred.mathworks.com>
References: <b9bb3ca1-66f4-4c5f-9553-cd970bfb7eb1@v4g2000vba.googlegroups.com> <gtvnh1$nrf$1@fred.mathworks.com> <gtvoba$hrd$1@fred.mathworks.com> <gtvp9b$ka8$1@fred.mathworks.com> <gtvt1a$leg$1@fred.mathworks.com>
Reply-To: <HIDDEN>
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 1241747581 22540 172.30.248.38 (8 May 2009 01:53:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 8 May 2009 01:53:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1440443
Xref: news.mathworks.com comp.soft-sys.matlab:538393


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gtvt1a$leg$1@fred.mathworks.com>...
> > 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.
> > 
> 
> The example you gave can be still considered as intersection of half planes Matt. In the definition the matrix A and b can have infinity number of rows (A is just a linear operator between two vectorial spaces, no need to be R^m to R^n).
> 
> I assume the computer does not have infinity memory, of A and b is finite matrix. And yes, if they are finite, vertexes are indeed defined when A has finite size.

So you would approximate the convex hull with a polyhedron and then apply your vertex searching method? Is it clear how many vertices and where the vertices need to be placed to get a sufficiently good approximation? And couldn't the required number of vertices be prohibitvely large if your method is O(N^2) or higher?