CGAL users discussion list

[Maarten Moesen <>]

Dear CGAL community,

For a literature review, I would like to ask a number of things which  
are still not really clear for me after studying the manual and doing  
some literature searches:

Regarding the straight skeleton:
* The runtime complexity of the straight skeleton, is it indeed O(nr +  
n log n), with n = total nb vertices and r = nb reflex vertices, like  
in the implementation of Felkel?
* What publication can I best refer to address its runtime complexity  
(as its not mentioned in the manual)?

Regarding the hilbert_sort and spatial_sort algorithms:
http://www.cgal.org/Manual/last/doc_html/cgal_manual/Spatial_sorting/Chapter_main.html

* Here also: what is their runtime complexity?
* Are there publications that explain the algorithms used and provide  
some benchmarks on spatial locality improvement?

Thanks a lot!

Maarten Moesen


> You may find the answer to your question
> in the CGAL documentation.
> I quote below the definition of Alpha-shapes in CGAL's user manual
> http://www.cgal.org/Manual/last/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html
>
> More precisely, the definition of alpha shapes is based on an  
> underlying triangulation that may be a Delaunay triangulation in  
> case of basic alpha shapes or a regular triangulation (cf. 35.3) in  
> case of weighted alpha shapes.
>
> Let us consider the basic case with a Delaunay triangulation. We  
> first define the alpha complex of the set of points S. The alpha  
> complex is a subcomplex of the Delaunay triangulation. For a given  
> value of α, the alpha complex includes all the simplices in the  
> Delaunay triangulation which have an empty circumsphere with squared  
> radius equal or smaller than α. Here ``empty'' means that the open  
> sphere do not include any points of S. The alpha shape is then  
> simply the domain covered by the simplices of the alpha complex (see  
> [EM94]).
>
> mahdavi wrote:
> > hi all
> > I use alpha complex ,my program is used regular triangulation  for   
> > weighted
> > points and I  want to  grow points  by constant alpha(a). please  
> > anybody say
> > me that in weighted alpha  complex must be used alpha or square  
> > alpha ,
> > //////////////////////////////////////////////////////////////////////
> > Which is instruction correct?
> > 1:Alpha_shape_3  as(P1.begin(), P1.end(), a, Alpha_shape_3::GENERAL);
> > 2:Alpha_shape_3  as(P1.begin(), P1.end(),  
> > a^2 ,Alpha_shape_3::GENERAL);
> > thanks.
>
> --
> Mariette Yvinec
> Geometrica project team
> INRIA  Sophia-Antipolis

--
Maarten Moesen, PHD
Department of Metallurgy and Materials Engineering (MTM)
K.U.Leuven
Kasteelpark Arenberg 44 - Bus 02450
B-3001 Heverlee, Belgium
tel. +32 (0)16 32 13 17
fax. +32 (0)16 32 19 90