Finding a vector within a specified range of angles from other vectors

Question

Take $v_1,v_2,\ldots,v_k\in \mathbb{R}^n$. Is there a way of finding some $x\in\mathbb{R}^n$, given the inequalities $l_i\leq\theta_i\leq u_i$ where $\theta_i$ is the angle between $x$ and $v_i$, or proving that such an $x$ exists?

Answer 1

It would be helpful if you give a bit more background on the reason for your question. Why do you need this? What do you want to do with this? Are the various numbers $l_i , u_i$ random, fixed or related and the same for the vectors. Are you looking for a numerical answer/method or something analytical? Without knowledge of any of these thing it not possible to give a good answer.

In the general case without additional information one can only try and find a vector ${\bf x}$ in a systematic fashion. This can be done more efficiently by analysing the set of vectors ${\bf v}_i$ in detail, for instance if there is an $1 \leq i<j \leq k$ such that $\arccos({\bf v}_i \cdot {\bf v}_j) >u_i + u_j$ there is no ${\bf x}$ that can satisfy all the constraints. In particular the small $u_i$ are relevant for such an approach.

A very simple method would be to generate random points on a unit sphere that represent the direction of ${\bf x}$ and check whether they satisfy all of the constraints. The disadvantage is of course that if you do not find a good direction, you still don't know whether it exist or not.

In a more systematic way you need to consider ${\bf v}_1$ and ${\bf v}_1$ and find the area on the unit sphere that is allowed by their simultaneous constraints. Successively adding more ${\bf v}_i$ will diminish the area on the unit sphere that is allowed. The process stops whenever the area completely vanishes, or you run out of vectors ${\bf v}_i$. Problematic here is the fact that the area most likely will consists of various disjoint parts of the unit sphere each of which is bounded by a subset of the set of constraints. Alternatively, one could make imperfect representation of the allowed area by a discretisation of the unit sphere, for instance a fine triangulation mesh, and keep track of which of the triangles is completely allowed and which ones are intersected by one or more constraints.