How to find an orientation in 3d to maximize the minimum of three vectors' projections?

Question

I have a solid geometry problem. I have three vectors in 3d. I would like to find an orientation to maximize the minimum of these three vectors' projections. I explain my problem with following example. My three vectors are [0,0,1],[0,1,0] and [1,1,0]. If my orientation nt1 is [0,1,0], the length of the projection of three vectors on orientation nt1 are{ 0,1,1}. So the minimum of it is zero. If my orientation nt2 is [0.707,0.707,0], the length of projections are {0.707,0.707,1.414}. The minimum of it is 0.707. I would like to find the best orientation to maximize this minimum of projections. Could you give me any suggestion or key word of this problem? I have no idea how to deal with it. Thank you.

Answer 1

More generally, the orientation vector, $v$, can be found with gradient descent by taking steps towards the vector with the smallest projection until $v$ stabilizes to oscillating between a subset of the vectors. For convergence, decrease the step size.

If the vector entries are not restricted to positive values, this vector may not be optimal. A different perspective could be useful here:

Consider the dual question of finding the hyperplane orthogonal to the orientation vector. The problem can be restated as finding the hyperplane, passing through the origin, which maximizes the minimum distance from points to the plane.

The hyperplane partitions the points based on the sign of the projection. Gradient descent will provide the optimal orientation $v$, assuming we start with the correct partition.

Finding the appropriate partition can be difficult in higher dimensions. However, there are very good clustering algorithms for tackling this problem.

Answer 2

The optimal orientation is v = [0,1,1]. With positive entries for v, $[0,1,1]\cdot v \geq [0,1,0] \cdot v $ , so we don't need to worry about [0,1,1]. The other two are symmetric, so we balance them.