Parallel Geometric Algorithms for Multi-Core Computers (2009)
Batista, Vicente, Millman, David, Pion, Sylvain, Singler, Johannes
Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the...
Parallel Geometric Algorithms for Multi-Core Computers (2009)
Batista, Vicente, Millman, David, Pion, Sylvain, Singler, Johannes
Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the...
3. The Curved Kernel 4. The Algebraic Kernel 5. The Arrangement Traits Outline (2008)
Elias Tsigaridas, Ioannis Emiris, Monique Teillaud, Sylvain Pion, Arrangement Of Lines
Pedro Machado, Manhães Castro, Sylvain Pion, Monique Teillaud
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 An algebraic kernel for circles was released in CGAL 3.2, as part of the CGAL 2D Circular Kernel....
Guillaume Melquiond, Sylvain Pion
Abstract. Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical...
under the “Information Society Technologies” (2008)
Athanasios V. Kakargias, Sylvain Pion, Athanasios V. Kakargias, Sylvain Pion
This report describes some adjustments that have been made to the Curved Kernel. Some of them have been made with performance in mind, others for interoperability and some, necessary modifications...
Principal Component Analysis in CGAL (2008)
Gupta, Ankit, Alliez, Pierre, Pion, Sylvain
Principal component analysis is a basic component of many geometric computing and processing algorithms. It is most commonly used on point sets, although applicable as well to sets of arbitrary...
Principal Component Analysis in CGAL (2008)
Gupta, Ankit, Alliez, Pierre, Pion, Sylvain
Principal component analysis is a basic component of many geometric computing and processing algorithms. It is most commonly used on point sets, although applicable as well to sets of arbitrary...
Parallel Geometric Algorithms for Multi-Core Computers (2008)
Batista, Vicente, Millman, David, Pion, Sylvain, Singler, Johannes
Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the...
FPG: A code generator for fast and certified geometric predicates (2008)
We present a general purpose code analyzer and generator for filtered predicates, which are critical for geometric algorithms. While there already exist such code generators, our contribution...
FPG: A code generator for fast and certified geometric predicates (2008)
We present a general purpose code analyzer and generator for filtered predicates, which are critical for geometric algorithms. While there already exist such code generators, our contribution...
Parallel Geometric Algorithms for Multi-Core Computers (2008)
Batista, Vicente, Millman, David, Pion, Sylvain, Singler, Johannes
Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the...
Robust Construction of the Three-Dimensional Flow Complex (2008)
Cazals, Frédéric, Parameswaran, Aditya, Pion, Sylvain
The Delaunay triangulation and its dual the Voronoi diagram are ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and...
Directed Rounding Arithmetic Operations in C++ (2008)
Melquiond, Guillaume, Pion, Sylvain
We propose the addition of new functions to the C++0x standard library that provide floating-point operations (+, -, *, /, sqrt and fma) as well as conversion functions with directed rounding. This...
Directed Rounding Arithmetic Operations in C++ (2008)
Melquiond, Guillaume, Pion, Sylvain
We propose the addition of new functions to the C++0x standard library that provide floating-point operations (+, -, *, /, sqrt and fma) as well as conversion functions with directed rounding. This...
Robust Construction of the Three-Dimensional Flow Complex (2008)
Cazals, Frédéric, Parameswaran, Aditya, Pion, Sylvain
The Delaunay triangulation and its dual the Voronoi diagram are ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and...
Classroom examples of robustness problems in geometric computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause...
Classroom examples of robustness problems in geometric computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause...
Classroom Examples of Robustness Problems in Geometric Computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (2007)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
1 CGAL: an overview CGAL, the Computational Geometry Algorithms Library (2007)
Jean-daniel Boissonnat, Frank Da, Olivier Devillers, Sylvain Pion, Monique Teillaud, Mariette Yvinec
is a large scaled project funded by the European Community. Its goal is to develop a body of objects and operations commonly used in computational geometry and to make them available to application...
Susan Hert, Michael Hoffmann, Sylvain Pion, Michael Seel
Abstract. Geometric algorithms are based on geometric objects such as points, lines and circles. The term kernel refers to a collection of representations for constantsize geometric objects and...
Olivier Devillers, Olivier Devillers, Sylvain Pion, Sylvain Pion, Projets Prisme
apport de recherche
Exact and efficient computations on circles in CGAL and applications to VLSI design (2007)
Teillaud, Monique, De Castro, Pedro, Pion, Sylvain
CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. CGAL currently offers mostly functionalities for linear objects (points,...
Exact and efficient computations on circles in CGAL and applications to VLSI design (2007)
Teillaud, Monique, De Castro, Pedro, Pion, Sylvain
CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. CGAL currently offers mostly functionalities for linear objects (points,...
Exact and efficient computations on circles in CGAL and applications to VLSI design (2007)
De Castro, Pedro, Pion, Sylvain, Teillaud, Monique
CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. CGAL currently offers mostly functionalities for linear objects (points,...
Exact and efficient computations on circles in CGAL and applications to VLSI design (2007)
De Castro, Pedro, Pion, Sylvain, Teillaud, Monique
CGAL (Computational Geometry Algorithms Library) is a large collection of geometric objects, data structures and algorithms. CGAL currently offers mostly functionalities for linear objects (points,...
Formally Certified Floating-Point Filters For Homogeneous Geometric Predicates (2007)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
Formally Certified Floating-Point Filters For Homogeneous Geometric Predicates (2007)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
An Adaptable and Extensible Geometry Kernel (2007)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term kernel refers to a collection of representations for constant-size geometric objects and operations on...
An Adaptable and Extensible Geometry Kernel (2007)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term kernel refers to a collection of representations for constant-size geometric objects and operations on...
An adaptable and extensible geometry kernel (2007)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term kernel refers to a collection of representations for constant-size geometric objects and operations on...
Algebraic Issues in Computational Geometry (2007)
Mourrain, Bernard, Pion, Sylvain, Schmitt, Susanne, Técourt, Jean-Pierre, Tsigaridas, Elias, Wolpert, Nicola
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
De la géométrie algorithmique au calcul géométrique (2006)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A proposal for the C++ standard : Bool_set, multi-valued logic (2006)
Pion, Sylvain, Melquiond, Guillaume, Brönnimann, Hervé
We propose a design for multi-valued logic, for integration into the C++ standard. The main motivation for this class comes from interval arithmetic, where it can be conveniently used as return type...
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
The design of the Boost interval arithmetic library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We present the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. Interval computations are an essential tool for...
The design of the Boost interval arithmetic library (2006)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We present the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. Interval computations are an essential tool for...
Constructive root bound for k-ary rational input numbers (2006)
Guaranteeing accuracy is the critical capability in exact geometric computation, an important paradigm for constructing robust geometric algorithms. Constructive root bounds is the fundamental...
Constructive root bound for k-ary rational input numbers (2006)
Guaranteeing accuracy is the critical capability in exact geometric computation, an important paradigm for constructing robust geometric algorithms. Constructive root bounds is the fundamental...
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
A Generic Lazy Evaluation Scheme for Exact Geometric Computations (2006)
We present a generic C++ design to perform efficient and exact geometric computations using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms....
Reply to "Backward Error Analysis ..." (2006)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Gavrilova, Marina, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause implementations...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2006)
Pion, Sylvain, Brönnimann, Hervé, Melquiond, Guillaume
I will report on a recent effort by Guillaume Melquiond, Hervé Br"onnimann and myself to push forward a proposal to include interval arithmetic in the next C++ ISO standard. The goals of the...
Formally certified floating-point filters for homogeneous geometric predicates (2005)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
A Proposal to add Interval Arithmetic to the C++ Standard Library (2005)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
Interval arithmetic is a basic tool for certified mathematical computations, it is presented in many references. We describe here the formal proposal to include interval arithmetic in the C++...
Formally certified floating-point filters for homogeneous geometric predicates (2005)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
Formally certified floating-point filters for homogeneous geometric predicates (2005)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
Recent progress in exact geometric computation (2005)
Li, Chen, Pion, Sylvain, Yap, Chee
Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving...
Recent progress in exact geometric computation (2005)
Li, Chen, Pion, Sylvain, Yap, Chee
Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving...
Formal certification of arithmetic filters for geometric predicates (2005)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
Formal certification of arithmetic filters for geometric predicates (2005)
Melquiond, Guillaume, Pion, Sylvain
Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner,Lutz, Mehlhorn,Kurt, Pion,Sylvain, Schirra,Stefan, Yap,Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
An empirical comparison of software for constructing arrangements of curved arcs (2004)
Berberich,Eric, Eigenwillig,Arno, Emiris,Ioannis, Fogel,Efraim, Hemmer,Michael, Halperin,Dan, ...
Classroom examples of robustness problems in geometric computations (2004)
Kettner,Lutz, Mehlhorn,Kurt, Pion,Sylvain, Schirra,Stefan, Yap,Chee
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
An empirical comparison of software for constructing arrangements of curved arcs (2004)
Berberich, Eric, Eigenwillig, Arno, Emiris, Ioannis, Fogel, Efraim, Hemmer, Michael, Halperin, Dan, ...
Classroom examples of robustness problems in geometric computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
Towards an Open Curved Kernel (2004)
Emiris, Ioannis, Kakargias, Athanasios, Pion, Sylvain, Teillaud, Monique, Tsigaridas, Elias
Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The kernel of the CGAL library provides several functionalities...
Towards an Open Curved Kernel (2004)
Emiris, Ioannis, Kakargias, Athanasios, Pion, Sylvain, Teillaud, Monique, Tsigaridas, Elias
Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The kernel of the CGAL library provides several functionalities...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Classroom Examples of Robustness Problems In Geometric Computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause implementations...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap, Inria Sophia
Abstract. The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Lutz Kettner, Kurt Mehlhorn, Kurt Mehlhorn, Sylvain Pion, Sylvain Pion, ...
Project funded by the European Community
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Efficient Exact Geometric Predicates for Delaunay Triangulations (2003)
Devillers, Olivier, Pion, Sylvain
A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....
Efficient Exact Geometric Predicates for Delaunay Triangulations (2003)
Devillers, Olivier, Pion, Sylvain
A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....
The Boost Interval Arithmetic Library (2003)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We report on the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. The design of the library is unique in that it...
Constructive Root Bound for k-Ary Rational Input Numbers (2003)
Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the...
The Boost Interval Arithmetic Library (2003)
Brönnimann, Hervé, Melquiond, Guillaume, Pion, Sylvain
We report on the design of the Boost interval arithmetic library, a C++ library designed to efficiently handle mathematical intervals in a generic way. The design of the library is unique in that it...
Constructive Root Bound for k-Ary Rational Input Numbers (2003)
Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the...
Constructive Root Bound for k-Ary Rational Input Numbers (2003)
Sylvain Pion And, Sylvain Pion, Chee Yap
Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the...
Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)
Devillers, Olivier, Pion, Sylvain
A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....
Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)
Devillers, Olivier, Pion, Sylvain
A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....
Walking in a Triangulation (2002)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
Walking in a Triangulation (2002)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
Efficient Exact Geometric Predicates for Delaunay Triangulations (2002)
Devillers, Olivier, Pion, Sylvain
A time efficient implementation of the exact computation paradigm relies on arithmetic filters which are used to speed up the exact computation of easy instances of the geometric predicates....
Walking in a Triangulation (2002)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
Boissonnat, Jean-Daniel, Devillers, Olivier, Pion, Sylvain, Teillaud, Monique, Yvinec, Mariette
This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.
Boissonnat, Jean-Daniel, Devillers, Olivier, Pion, Sylvain, Teillaud, Monique, Yvinec, Mariette
This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library CGAL.
An Adaptable and Extensible Geometry Kernel (2001)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term Kernel refers to a collection of representations for constant-size geometric objects and operations on...
Walking in a triangulation (2001)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
An Adaptable and Extensible Geometry Kernel (2001)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term Kernel refers to a collection of representations for constant-size geometric objects and operations on...
Walking in a triangulation (2001)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
An Adaptable and Extensible Geometry Kernel (2001)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term Kernel refers to a collection of representations for constant-size geometric objects and operations on...
Walking in a triangulation (2001)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (2001)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be...
Walking in a Triangulation (2001)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (2001)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be...
Walking in a Triangulation (2001)
Devillers, Olivier, Pion, Sylvain, Teillaud, Monique
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different strategies.
An Adaptable and Extensible Geometry Kernel (2001)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term Kernel refers to a collection of representations for constant-size geometric objects and operations on...
An Adaptable and Extensible Geometry Kernel (2001)
Hert, Susan, Hoffmann, Michael, Kettner, Lutz, Pion, Sylvain, Seel, Michael
Geometric algorithms are based on geometric objects such as points, lines and circles. The term Kernel refers to a collection of representations for constant-size geometric objects and operations on...
Walking in a triangulation (2001)
Olivier Devillers, Sylvain Pion, Monique Teillaud
Given a triangulation in the plane or a tetrahedralization in 3-space, we investigate the efficiency of locating a point by walking in the structure with different
An adaptable and extensible geometry kernel (2001)
Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, Michael Seel
ii
Walking in a triangulation (2001)
Olivier Devillers, Olivier Devillers, Sylvain Pion, Sylvain Pion, Monique Teillaud, Monique Teillaud, ...
apport de recherche
Walking in a Triangulation (2001)
Olivier Devillers, Sylvain Pion, Monique Teillaud, Thème Génie Logiciel, Projets Prisme, ...
Given a triangulation in the plane or a tetrahedralization in 3-space, weinvestigate the e#ciency of locating a pointbywalking in the structure with di#erent strategies. Key-words: Computational...
An Empirical Comparison of Software for Constructing Arrangements of Curved Arcs (2000)
Sylvain Pion, Monique Teillaud, Efraim Fogel, Dan Halperin, Ron Wein, Ioannis Emiris, ...
Arrangements of planar curves are fundamental structures in computational geometry.
De la géométrie algorithmique au calcul géométrique (1999)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
De la géométrie algorithmique au calcul géométrique (1999)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
De la géométrie algorithmique au calcul géométrique (1999)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
De la géométrie algorithmique au calcul géométrique (1999)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
De la géométrie algorithmique au calcul géométrique (1999)
Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant...
Interval Arithmetic: an efficient implementation and an application to computational geometry (1999)
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe a C++ implementation of interval arithmetic that is strongly influenced by the rounding modes...
Sign Determination in Residue Number Systems (1999)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We...
Interval Arithmetic: an efficient implementation and an application to computational geometry (1999)
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe a C++ implementation of interval arithmetic that is strongly influenced by the rounding modes...
Sign Determination in Residue Number Systems (1999)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We...
Programming with CGAL: the example of triangulations (1999)
Boissonnat, Jean-Daniel, Cazals, Frédéric, Da, Tran Kai Frank, Devillers, Olivier, Pion, Sylvain, Rebufat, Francois, ...
This paper accompanies a video presenting how to develop code using CGAL, in particular, the triangulation classes.
Programming with CGAL: the example of triangulations (1999)
Boissonnat, Jean-Daniel, Cazals, Frédéric, Da, Tran Kai Frank, Devillers, Olivier, Pion, Sylvain, Rebufat, Francois, ...
This paper accompanies a video presenting how to develop code using CGAL, in particular, the triangulation classes.
Interval arithmetic: an efficient implementation and an application to computational geometry (1999)
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe a C++ implementation of interval arithmetic that is strongly inAEuenced by the rounding modes...
Sign Determination in Residue Number Systems (1999)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Brönnimann, Hervé, Burnikel, Christoph, Pion, Sylvain
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Hervé Brönnimann, Herv Br#nnimann, Sylvain Pion, Christoph Burnikel
We discuss interval techniques for speeding up the exact evaluation of geometric predicates and describe an efficient implementation of interval arithmetic that is strongly influenced by the rounding...
Interval Arithmetic Yields Efficient Dynamic Filters for Computational Geometry (1998)
Herve Brönnimann, Christoph Burnikel, Sylvain Pion
We discuss floating-point filters as a means of restricting the precision needed for arithmetic operations while still computing the exact result. We show that interval techniques can be used to...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Exact rounding for geometric constructions (1997)
Brönnimann, Hervé, Pion, Sylvain
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Exact rounding for geometric constructions (1997)
Brönnimann, Hervé, Pion, Sylvain
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Computing exact geometric predicates using modular arithmetic with single precision (1997)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computing exact geometric predicates using modular arithmetic with single precision (1997)
Brönnimann, Hervé, Emiris, Ioannis, Pan, Victor, Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Exact Rounding for Geometric Constructions (1997)
Hervé Brönnimann, Sylvain Pion
Exact rounding is provided for elementary floating-point arithmetic operations (e.g. in the IEEE standard). Many authors have felt that it should be provided for other operations, in particular for...
Exact Modular Arithmetic With Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Ioannis Z. Emiris, Victor Y. Pan, ...
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...