Perturbations in CGAL

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Perturbations in CGAL

Ashwin Nanjappa-2
Hi,

I recently read the paper "An Easy to Use Implementation Of Linear
Perturbations Within CGAL" [1]. The authors describe random linear
perturbations they applied onto the input point set. The paper also lists
some perturbation types/classes/functions in CGAL like
CGAL_Epsilon_polynomial and CGAL_perturb. I couldn't find any of these in
the current CGAL documentation, except for perturb_points_2().

Are there any other implementations/examples of random linear perturbation
in the current version of CGAL?

[1] <http://dx.doi.org/10.1007/3-540-48318-7_15>

Regards,
~ash
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Sylvain Pion
Administrator
Ashwin Nanjappa a écrit :

> Hi,
>
> I recently read the paper "An Easy to Use Implementation Of Linear
> Perturbations Within CGAL" [1]. The authors describe random linear
> perturbations they applied onto the input point set. The paper also
> lists some perturbation types/classes/functions in CGAL like
> CGAL_Epsilon_polynomial and CGAL_perturb. I couldn't find any of these
> in the current CGAL documentation, except for perturb_points_2().
>
> Are there any other implementations/examples of random linear
> perturbation in the current version of CGAL?
AFAIK, this work has not made its way into CGAL.

Some parts of CGAL use some dedicated perturbation schemes
(like Delaunay triangulations).

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/


smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Ashwin Nanjappa-2
Sylvain Pion wrote:
>
> AFAIK, this work has not made its way into CGAL.
>
> Some parts of CGAL use some dedicated perturbation schemes
> (like Delaunay triangulations).

I kind of guessed so. Else, if perturbed inputs were used, the algorithms
donot need to check for degeneracy, which I see that they still do. There
would be some post-processing after the algorithm though.

~ash
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Monique Teillaud
In reply to this post by Ashwin Nanjappa-2
Hi,

 From the url you give, the title of [1] actually mentions "Cupgal", not
CGAL, and this is quite an old paper. I am not sure what was integrated
in CGAL.

For instance, the abstract (I have not read the paper) of [1] mentions
Delaunay triangulations, which actually don't use these random linear
perturbations at all in CGAL. The CGAL 3D Triangulation uses symbolic
perturbations,
- introduced in a SODA paper: http://hal.inria.fr/inria-00166710/
- generalized here: https://hal.inria.fr/inria-00090522
(journal version in preparation)

best,
        Monique Teillaud

Ashwin Nanjappa wrote:

> Hi,
>
> I recently read the paper "An Easy to Use Implementation Of Linear
> Perturbations Within CGAL" [1]. The authors describe random linear
> perturbations they applied onto the input point set. The paper also
> lists some perturbation types/classes/functions in CGAL like
> CGAL_Epsilon_polynomial and CGAL_perturb. I couldn't find any of these
> in the current CGAL documentation, except for perturb_points_2().
>
> Are there any other implementations/examples of random linear
> perturbation in the current version of CGAL?
>
> [1] <http://dx.doi.org/10.1007/3-540-48318-7_15>
>
> Regards,
> ~ash

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Monique Teillaud
[hidden email] wrote:
> Hi,
>
>  From the url you give, the title of [1] actually mentions "Cupgal", not
> CGAL,

(In fact this is a mistake on the springerlink web pages... The title on
the paper itself is CGAL, as you wrote)

> and this is quite an old paper. I am not sure what was integrated
> in CGAL.
>
> For instance, the abstract (I have not read the paper) of [1] mentions
> Delaunay triangulations, which actually don't use these random linear
> perturbations at all in CGAL. The CGAL 3D Triangulation uses symbolic
> perturbations,
> - introduced in a SODA paper: http://hal.inria.fr/inria-00166710/
> - generalized here: https://hal.inria.fr/inria-00090522
> (journal version in preparation)
>
> best,
>     Monique Teillaud
>
> Ashwin Nanjappa wrote:
>
>> Hi,
>>
>> I recently read the paper "An Easy to Use Implementation Of Linear
>> Perturbations Within CGAL" [1]. The authors describe random linear
>> perturbations they applied onto the input point set. The paper also
>> lists some perturbation types/classes/functions in CGAL like
>> CGAL_Epsilon_polynomial and CGAL_perturb. I couldn't find any of these
>> in the current CGAL documentation, except for perturb_points_2().
>>
>> Are there any other implementations/examples of random linear
>> perturbation in the current version of CGAL?
>>
>> [1] <http://dx.doi.org/10.1007/3-540-48318-7_15>
>>
>> Regards,
>> ~ash
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Ashwin Nanjappa-2
In reply to this post by Monique Teillaud
[hidden email] wrote:
[...]
> Delaunay triangulations, which actually don't use these random linear
> perturbations at all in CGAL. The CGAL 3D Triangulation uses symbolic
> perturbations,
> - introduced in a SODA paper: http://hal.inria.fr/inria-00166710/
> - generalized here: https://hal.inria.fr/inria-00090522
> (journal version in preparation)

These papers are useful to me to understand perturbations in CGAL, thanks
for pointing them out.

Regards,
~ash
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Perturbations in CGAL

Monique Teillaud
Ashwin Nanjappa wrote:

> [hidden email] wrote:
> [...]
>
>> Delaunay triangulations, which actually don't use these random linear
>> perturbations at all in CGAL. The CGAL 3D Triangulation uses symbolic
>> perturbations,
>> - introduced in a SODA paper: http://hal.inria.fr/inria-00166710/
>> - generalized here: https://hal.inria.fr/inria-00090522
>> (journal version in preparation)
>
>
> These papers are useful to me to understand perturbations in CGAL,
> thanks for pointing them out.

Note that the perturbation explained there is specific to
Delaunay/regular triangulations, it is not a general scheme.
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss