Results 1 to 9 of 9

Math Help - convex sets and polyhedrons

  1. #1
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128

    convex sets and polyhedrons

    if S is a set in the euclidean vector space U with inner product and norm defined in it, a point x in S is called an extreme pt of S if x is not interior to any segment contained in S.
    is there an intuitive way of thinking about this?

    1. what would be an example of bounded and convex set without extreme points?
    2. suppose S is a polyhedron. is it true in general that if x in S is not interior to S, then x is an extreme pt of of S?
    3. given linear functionals g_k:R^2->R, and real numbers b_k with k=1,2,3,4, and polyhedron S determined by g_k(x)<=b_k, is it possible for S to have 7 or more extreme pts? if not, how many extreme points can S have at most?

    i have an idea for #1 (would it be ok to consider some open set in R^2? say an open halfspace defined by x>0) , but i don't really understand 2 and 3 (even though i have this feeling that 2 must be false). can someone help me?
    Last edited by squarerootof2; July 11th 2008 at 08:41 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by squarerootof2 View Post
    if S is a set in the euclidean vector space U with inner product and norm defined in it, a point x in S is called an extreme pt of S if x is not interior to any segment contained in S.
    is there an intuitive way of thinking about this?

    1. what would be an example of bounded and convex set without extreme points?
    In two dimensions think of the interior of a convex polygon, such a region is closed and bounded but has no extreme points.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by squarerootof2 View Post
    2. suppose S is a polyhedron. is it true in general that if x in S is not interior to S, then x is an extreme pt of of S?
    Does your definition of a polyhedron permit holes?

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    the definition of polyhedron i have is that a polyhedron is an intersection of finitely many closed halfspaces (closed/convex set)

    the way closed half space is defined is, let U be a euclidean vector space, and recall if g:U->R is a linear functional and if b is a real number, then the set {x:g(x)<=b} is called a close half space.

    how would change of definitions change our answer?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    Quote Originally Posted by CaptainBlack View Post
    In two dimensions think of the interior of a convex polygon, such a region is closed and bounded but has no extreme points.

    RonL
    basically this would be the open ball in the regular topology right? i was just thinking about this example.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by squarerootof2 View Post
    2. suppose S is a polyhedron. is it true in general that if x in S is not interior to S, then x is an extreme pt of of S?
    Think about a point that lies on an edge of the polyhedron (but not at a vertex). It is not in the interior, but it is not extreme.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    ah yes i was thinking of the example of the edge point. what would be the procedure to prove that it's not an extreme point?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by squarerootof2 View Post
    ah yes i was thinking of the example of the edge point. what would be the procedure to prove that it's not an extreme point?
    If for example you choose the midpoint of an edge, then it's halfway between two vertices. So it is a nontrivial convex combination of two points in the set. That is effectively the definition of a non-extreme point.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    thanks for help on 1 and 2, i was able to successfully prove those problems. but for part c, is the correct answer 4? i've been drawing a bunch of lines and it seems like at most 4 vertex points can be attained from the intersection of four closed half-spaces. is my logic wrong?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 10th 2010, 06:14 AM
  2. are these sets are convex or not?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 16th 2010, 11:42 AM
  3. convex sets
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 3rd 2010, 10:30 AM
  4. The union of two convex sets is not convex
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 30th 2010, 03:23 PM
  5. Convex Sets
    Posted in the Calculus Forum
    Replies: 0
    Last Post: October 5th 2007, 06:43 PM

Search Tags


/mathhelpforum @mathhelpforum