CGAL users discussion list

[Илья Палачев <>]

Hi,

 

If this is not the right place this question, please redirect me :)

 

I'm solving some computational problem, and there is a question for which I have not have enough experience in computational geometry. Maybe you can advise some methods that are already implemented in CGAL for that?

 

Here is the problem.

 

Let U = {u_1, u_2, ..., u_n} be the finite set of points on the unit sphere in R^3.

 

Definition: Quadruple of points (u_i, u_j, u_k, u_l) is said to be positive if there exists a_ij > 0, a_ik > 0, a_il > 0 such that:

 

u_i = a_ij * u_j + a_ik * u_k + a_il * u_l

 

 

Definition. Positive quadruple (u_i, u_j, u_k, u_l)  is said to be local relatively to the set U if no such u_s in the set U 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?

 

It seems to me that Delaunay triangulation can help in this case, but in practice there can happen the sitatuation when points u_i, u_j, u_k, u_l are located quite far from each other on the Delaunay triangulation.

 

Any ideas?

 

--

Best regards,

Ilya Palachev