CGAL users discussion list

[thierry Fernandez <>]

This is reminiscent of the barycentric coordinates.

point must be in triangle

2015-02-18 17:10 GMT+01:00 Olivier Devillers <>:

Le 18/02/15 16:57, Илья Палачев a écrit :

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.

If I rephrase your problem in the plane:

Find all quadruple (u_i,u_j,u_k,u_l) such that u_i is the only point of U innside triangle u_j u_k u_l.


Rq: You have Theta(n^3) solutions
Upper bound:
   you have n^3 choices for the triangle, then there is no choice for the point inside it.
Lower bound
 ---  n/3 points on segment [(0,-10),(1,-10)]   (possible u_j)
 ---  n/3 points on segment [(0,10),(1,10)]   (possible u_k)
 ---  n/3 points on segment [(-10,-1),(-10,1)]   (possible u_l)
 ---  the origin  (possible u_i)


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss