Subject: CGAL users discussion list
List archive
- 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
- [cgal-discuss] Fast search of local positive quadruples on the sphere, Илья Палачев, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Olivier Devillers, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, thierry Fernandez, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Илья Палачев, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Olivier Devillers, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, thierry Fernandez, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Илья Палачев, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Илья Палачев, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Olivier Devillers, 02/19/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Илья Палачев, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Olivier Devillers, 02/18/2015
- Re: [cgal-discuss] Fast search of local positive quadruples on the sphere, Olivier Devillers, 02/18/2015
Archive powered by MHonArc 2.6.18.