CGAL users discussion list

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

 

 

18.02.2015, 19:11, "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)

 

Okay :)

 

Let's say that we have real-world example: we know that all points lie on the plane in some regular order...Not uniform distribution, but... something like that... say: points are uniformly distributed on the sphere and then pertrurbed from their initial position.

Stupid exhaustive search shows that there are only O(n) local positive quadruples. How can we find them?

 

Can you suggest anything more fast that the exhaustive search?

 

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