Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Is there any algorithm for Caratheodory theorem (convex hull)?
Replies: 5   Last Post: May 20, 2010 4:45 PM

 Messages: [ Previous | Next ]
 Robert Israel Posts: 11,902 Registered: 12/6/04
Re: Is there any algorithm for Caratheodory theorem (convex hull)?
Posted: May 19, 2010 4:13 PM

On Wed, 19 May 2010, Yihong wrote:

> If we know how P can be written as a convex combination of _finite_ points in A, then we know how to proceed inductively. This is essentially how the proof of the Caratheodory theorem is done. The problem now is I do not know how to do the first step. I only know P, as an expectation, lies in the convex hull of the image.

In this case I might start by taking a random sample of size n+1 from your
random variable, and keep increasing the size of the sample until P
is in the convex hull of the sample points.

Robert Israel israel@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

>> In article
>> <931825785.184920.1274257295244.JavaMail.root@gallium.
>> mathforum.org>,
>> Yihong <yihongwu@princeton.edu> wrote:
>>

>>> I have a question about the constructive aspects of
>>> Caratheodory theorem,
>>> which states that any point P in the convex hull of
>>> A \subset R^n can be
>>> written as the convex combination of at most n+1
>>> points in A.
>>>
>>> This is an existence result. I wonder if there is
>>> any algorithm that can give
>>> these n+1 points. In the problem I have A is the
>>> image of some continuous
>>> function f: R->R^n, and P = E[f(X)] for some random
>>> variable X.
>>>
>>> Thanks!

>>

>> I guess you need to apply induction, together with:
>> given k points,
>> constructively determine whether the affine span has
>> dimension less
>> than k-1, and if so, constructively write one of the
>> points as a convex
>> combination of the others.
>>
>> --
>> G. A. Edgar
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> http://www.math.ohio-state.edu/~edgar/

>

Date Subject Author
5/19/10 Yihong
5/19/10 G. A. Edgar
5/19/10 Yihong
5/19/10 Robert Israel
5/20/10 G. A. Edgar
5/20/10 Chip Eastham