CGAL users discussion list

[Olivier Devillers <>]

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.