7
$\begingroup$

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

$\endgroup$

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.