# Math Help - convex sets and polyhedrons

1. ## 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.

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?

2. Originally Posted by squarerootof2
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.

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

3. Originally Posted by squarerootof2
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

4. 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?

5. Originally Posted by CaptainBlack
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.

6. Originally Posted by squarerootof2
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.

7. 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?

8. Originally Posted by squarerootof2
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.

9. 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?