CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Francois Berenger wrote:
> On 07/11/2011 03:58 PM, Sebastien Loriot (GeometryFactory) wrote:
> > Your question is not clear to me. Can you elaborate?
>
> Hello,
>
> 1) I would like to know if it is possible to compute the surface
>    of a Nef polyhedra (I guess yes).
>    I don't need the exact procedure in fact, but for sure it would
>    educate me even if some CGAL expert just gives a rough idea.
This code is used to compute the Nef_3 boolean operations for example,
so it is working. I never try to use it with an inexact construction
kernel so I have no idea whether you could use it with such a kernel
(this is not possible for Nef_3 for example)

> 2) I'd like to have an idea of the complexity of the procedure
>    (O(n**something)?) to assess if it is worth doing with CGAL
>    or if an approximation of it would be faster.
This is computing an arrangement of great circle arcs on a sphere.
If I remember correctly, it is using two sweep algorithms, so the 
theoretical complexity should be something like O( (n+k)log(n) ) n being
the number of input and k the number of intersection points.

Note that there exists an experimental implementation using the CGAL
2D arrangement package doing something similar.
See this paper for example:
http://www.cs.tau.ac.il/~efif/publications/sphere_vor/sphere_vor.pdf

Sebastien.

> Regards,
> F.
>
> > Sebastien.
> >
> >
> > Francois Berenger wrote:
> > > Hello,
> > >
> > > Is it possible to compute the surface
> > > of the selected region as can be seen in
> > > the right hand part of figure Figure 21.1 from
> > > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Nef_S2/Chapter_main.html 
> > >
> > >
> > >
> > > Let's say we have N triangles on the sphere, would it be
> > > computationally intensive?
> > >
> > > Regards,
> > > F.