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: Olivier Devillers <>
  • To:
  • Subject: Re: [cgal-discuss] Fast search of local positive quadruples on the sphere
  • Date: Thu, 19 Feb 2015 09:29:42 +0100


Rephrasing again, given a set of points, you are searching the
empty triangles containing the origin O
(run this for all points but one ater choosing this one as origin)

We need to find points so that ABO is en empty triangle,
then try to combine ABO, BCO, CAO.

To do so, sort the points by polar order,
and get a star shaped polygon P.

Given u_i, u_i u_{i+1} O is a first triangle with u_i,
then compute the intersection of ray u_i u_{i+1} with P
to get the next candidate.

assuming ray tracing in log time
and that there are on average log triangles for each point A
you get O(n log^2 n) time when origin is chosen,
so O(n^2 log^2 n) in total for your problem.



Archive powered by MHonArc 2.6.18.

Top of Page