Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Fast search of local positive quadruples on the sphere

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Fast search of local positive quadruples on the sphere


Chronological Thread 
  • From: thierry Fernandez <>
  • To:
  • Subject: Re: [cgal-discuss] Fast search of local positive quadruples on the sphere
  • Date: Wed, 18 Feb 2015 17:15:38 +0100

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






Archive powered by MHonArc 2.6.18.

Top of Page