1

Let $C$ be a convex hull of finite set of points and lets assume dimension on $C$ is $n>0$ (so not a single point). Can we then claim that $C$ has facets? Facet F on my definition is a $n-1$ dimensional set that can be presented as $F=C\cap H$ where $H$ is some hyperplane supporting $C$.

I'm stuck here, any help is appreciated.

Elq
  • 74

1 Answers1

1

Yes, it has facets. Choose any $n$ of the defining points (since the dimension of $C$ is $n$, it has to have at least $n+1$ defining points). The hyperplane through these points divides space into two parts. If there are other defining points on both sides of the hyperplane, replace one of your original $n$ points with one of the others. Repeat, always choosing your new points from the same general direction. Because the set of defining points is finite, eventually, you will run out of new points to choose from. I.e., all the defining points not in your set will lie on the same side of the hyperplane. The points in your set will then define a facet of $C$.

Paul Sinclair
  • 43,643
  • Thx. I was thinking of something similar because this is obvious argument when you have only 3 dimension but I was lost in general case. But following your idea if I always pick the new point that is on say positive side of all previous hyperplanes then I must end up with a facet. – Elq May 15 '18 at 15:07
  • Yes. The facet you get depends on the choices you make, but as long as you don't keep switching back and forth in your directions, this will eventually lead you to a facet. – Paul Sinclair May 15 '18 at 16:56