I am a PhD. candidate student in Tsinghua University, China. I think this is an open problem in my field. That is:
How to find the smallest simplex which can enclose a bunch of given points in a high dimensional space (under the following two assumptions:)?
- (1) The number of the vertexes of the simplex is known, say n;
- (2) The number of the vertexes of the simplex is unknown.
To measure how small the simplex is, we can use the volume of the simplex.
The question is: can this problem be cast into a convex optimization?
Doesn't a simplex in n-space always have (n+1) vertices? Or would you want to allow for sub-dimensional simplices? But then, measuring the volume is quite pointless for all but the full-dimensional ones. I'm probably misunderstanding something, perhaps you can clarify this?
Yes, if a simplex in n-space having full dimension, then it has (n+1) vertices. But here we allow for sub-dimensional simplexes. I don't think measuring the volume of them is pointless if we constrain our focus to the sub affine set where the simplex resides. This is just like we can measure the area of a triangle in a 3 dimensional space. --Flyshcool 14:30, 1 July 2008 [GMT+8]