# Fast search of local positive quadruples on the sphere

Let $U = \{u_{1}, u_{2}, \ldots, u_{n}\} \subset \mathbb{R}^{3}$ be the finite set of points on the unit sphere in $\mathbb{R}^{3}$: $||u_{i}||_{2} = 1$

Definition: Quadruple of points $(u_{i}, u_{j}, u_{k}, u_{l})$ is said to be positive if $$\exists \alpha_{i j} > 0, \alpha_{i k} > 0, \alpha_{i l} > 0: u_{i} = \alpha_{i j} u_{j} + \alpha_{i k} u_{k} + \alpha_{i l} u_{l}$$

Definition: Positive quadruple $(u_{i}, u_{j}, u_{k}, u_{l})$ is said to be local relatively to the set U if $\nexists u_{s} \in U$ such that $(u_{s}, u_{j}, u_{k}, u_{l})$ is positive.

Question: Is there any fast algorithm to find all local positive quadruples in the given set $U$?

EDIT: Of course, in worst case the complexity of the algorithm should be $\Theta(n^3)$, since there is an example when there are $\Theta(n^3)$ local positive quadruples.

But suppose that $u_{i}$ are taken from some real-world example, and they are distributed on the sphere somehow uniformly (~close to uniform).

• cs.stackexchange.com since you are asking about runtime Feb 28 '15 at 17:35
• @johnmangual, thanks, I redirected this question to cs.stackexchange.com/questions/40024/… Mar 3 '15 at 13:48