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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.