## Hypercube vertex sampling with largest convex cone

Maybe this question was already asked and forgive me if I can't formulate it well.

Lets assume we have a n-dimensional hypercube. If we want the smallest set of vertices such that the cube is inside the convex cone of the vertices we can take all the vertices on the main coordinates - (1,0,0,..,0),(0,1,0,..,0) etc.

My question is what is the maximum number of vertices we can take, such that 1. No vertex is in the interior of the convex cone generated by these edges. 2. The cube is not contained in the convex cone of the vertices.

-

## 1 Answer

If you intend that the hypercube have a corner at the origin, and that the convex cone apex also be the origin, then for $n=3$, the cone that covers half the cube to one side of a diagonal plane seems to achieve the maximum:

This cone includes 6 of the 8 vertices on its boundary (including the origin/apex in this count). The natural generalization of this construction to the $n$-cube includes (if I've counted correctly) $$2^{n-1} + 2^{n-2} = 3 \cdot 2^{n-2}$$ vertices.

But perhaps I am misunderstanding your question, for your second condition on the cone seems superfluous.

-
 Yea, I believe your right. The reason I was looking for it is since I was looking at some kind of choosing from a worst case subset of the cube vertices that will allow receiving each of the vertices as an affine combination. Thank you! – ifog Nov 23 2011 at 14:48