Subject: CGAL users discussion list
List archive
- 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.
- [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.