Results 1 to 3 of 3

Math Help - Existence of a convex hull of few points in R^n ?

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    14

    Existence of a convex hull of few points in R^n ?

    Hi,

    I have a set of vectors V {v1,...,vk} where every element of V is from R^n. Please consider that k could be smaller than n.

    Does the convex hull C exist for the vectors in V ? so that v1,...,vk are elements of C

    If I write a vector v' as a convex combination of the vectors V, will v' be an element of C as well ?

    v'=c1*v1+...+ck*vk
    (where c1+...+ck = 1 and c1,..,ck positive)

    from my point of view it should work.

    consider for instance R^3.
    - two random vectors v1 and v2, form a convex set as a line which connects v1 and v2. Thus any vector on the line can be expressed as a convex combination of v1 and v2
    - three random vectors v1, v2, v3 form a triangle. And any convex combination will be inside the triangle
    - vector counts higher then the dimensions, would form a polyhedron and there could be interior vector as well (vectors inside the convex hull).

    It is clear to me for trivial example in low dimensional spaces. However Im not sure if this is valid for any dimensionality as well.

    kind regards,
    Andreas
    Last edited by sirandreus; January 14th 2008 at 02:47 AM. Reason: some corrections and additions
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    527
    Thanks
    7
    Does the convex hull C exist for the vectors in V ? so that v1,...,vk are elements of C

    Yes, ofcourse it does.

    If I write a vector v' as a convex combination of the vectors V, will v' be an element of C as well ?

    Most certainly.




    - two random vectors v1 and v2, form a convex set as a line which connects v1 and v2.
    The convex hull is the whole triangle.



    - three random vectors v1, v2, v3 form a
    Random tetrahedron, which (sides and interior included) forms the convex hull.




    But note that in more general spaces, the convex hull does not only consist of the set of convex combinations. Remember the Krein-Milman theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2007
    Posts
    14
    Hi Rebesques,

    thank your for your feedback.

    so in other words:

    if I have random vectors V={v1,...,vn} in R^n where V contains both extreme points and inner points, then I can write a vector v' as a convex combination v' = c1*v1+...+cn*vn and it will be sure that v' is in the same convex set, which contains the vectors V as well (without needing to calculate the convex hull of this convex set / without needing to distinguish the extreme points from the inner points)

    is this correct ?

    and also, the convex set which contains the vectors V, will be a subspace of R^n , right ?

    regards,
    Andreas
    Last edited by sirandreus; January 19th 2008 at 02:02 AM. Reason: an additional question
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. convex hull
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: January 15th 2012, 10:19 PM
  2. Convex Hull
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 31st 2010, 11:17 AM
  3. Optimization theory-convex hull help
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: January 21st 2010, 02:44 AM
  4. help with visualizing convex hull and polytope
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: October 31st 2009, 01:03 PM
  5. Convex hull and shortest path problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 19th 2007, 11:45 AM

Search Tags


/mathhelpforum @mathhelpforum