We study the relevance of algorithms for exact computation of the sign of a sum of floating-point numbers and error-free transformations of arithmetic expressions on floating-point numbers for the...
Federal Republic of Germany (2008)
Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Schirra, Christian Uhrig, ...
Abstract: We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time f~(n 2) where n is the number of obstacle corners. We...
A New Approach to Subdivision Simpli cation (2008)
Mark De Berg, Marc Van Kreveld, Stefan Schirra
The line simpli cation problem is an old and well-studied problem in cartography. Although there are several algorithms to compute a simpli cation, there seem to be no algorithms that perform line...
Geometric Computing with CGAL and LEDA (2008)
Abstract. LEDA and CGAL are platforms for combinatorial and geometric computing. We discuss the use of LEDA and CGAL for geometric computing and show that they provide a unique framework for exact,...
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
Lutz Kettner, Stefan Schirra, Remco Veltkamp
We report on the use of the generic programming paradigm in the computational geometry algorithms library cgal. The parameterization of the geometric algorithms in cgal enhances exibility and...
L. Paul Chew, Klara Kedem, Stefan Schirra
We investigate approximate decision algorithms for determining whether the minimum Hausdorff distance between two points sets (or between two sets of nonintersecting line segments) is at most...
Andreas Fabri, Geert-jan Giezeman, Stefan Schirra, Sven Schonherr
a computational geometry algorithms library
Stefan Schirra, Remco Veltkamp
Abstract. We report on the use of the generic programming paradigm in the computational geometry algorithms library cgal. The parameterization of the geometric algorithms in cgal enhances exibility...
Applications of the Generic Programming Paradigm in the Design of CGAL (2007)
Hervé Brönnimann, Lutz Kettner, Herv Br#nnimann, Stefan Schirra, Remco Veltkamp
We report on the use of the generic programming paradigm in the Computational Geometry Algorithms Library Cgal. The parameterization of the geometric algorithms in Cgal enhances flexibility and...
Omega Psi, Andreas Fabri, Andreas Fabri, Geert-jan Giezeman, Geert-jan Giezeman, Lutz Kettner, ...
Cgal is a Computational Geometry Algorithms Library written in C++, which is developed in an Esprit Ltr project. The goal is to make the large body of geometric algorithms developed in the field of...
Kurt Mehlhorn, Kurt Mehlhorn, Stefan Schirra, Stefan Schirra
Partially supported by ESPRIT project 28155 (GALIA). Work done while the second author was at Max-Planck-Institut fur Informatik. We prove a separation bound for a large class of algebraic...
Max-Planck-Institut fur Informatik (2007)
Mark De Berg, Marc Van Kreveld, Stefan Schirra
The line simplification problem is an old and well-studied problem in cartography. Although there are several algorithms to compute a simplification, there seem to be no algorithms that perform line...
This LEP is based on the rst author's Master's Thesis [9]. y (2007)
Jrg Schwerdt, Michiel Smid, Stefan Schirra, Fakultt Fr Informatik
This LEDA extension package solves the optimization problem that we call diameter problem for moving points and that is dened as follows. Denition 1.1 Let p be a point in the plane that is moving at...
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...
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...
The LEDA class real number - extended version (2004)
Funke,Stefan, Mehlhorn,Kurt, Schmitt,Susanne, Burnikel,Christoph, Fleischer,Rudolf, Schirra,Stefan
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...
The LEDA class real number - extended version (2004)
Funke, Stefan, Mehlhorn, Kurt, Schmitt, Susanne, Burnikel, Christoph, Fleischer, Rudolf, Schirra, Stefan
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
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...
Rahul Ray, Rahul Ray, Dekan Prof, Gutachter Prof, ...
Dedicated to my parents
Rahul Ray, Rahul Ray, Dekan Prof, Gutachter Prof, ...
Dedicated to my parents
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
A Case Study on the Portability of old CGAL Code (2004)
Stefan Schirra, Christian Schulz
In this abstract we report on our efforts to port ”a case study on the cost of geometric computing ” [5], which was based on release 1.2 of CGAL, to the latest release 3.0.1.
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...
Geometric Computing with CGAL and LEDA (2002)
Mehlhorn, Kurt, Schirra, Stefan
LEDA and CGAL are platforms for combinatorial and geometric computing. We discuss the use of LEDA and CGAL for geometric computing and show that they provide a unique framework for exact efficient...
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
A Separation Bound for Real Algebraic Expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Exact computation with leda real - theory and geometric applications (2001)
The number type leda real provides exact computation for a subset of real algebraic numbers: Every integer is a leda real, and leda reals are closed under the basic arithmetic operations +, −, ∗,...
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Exact computation with leda_real - Theory and geometric applications (2001)
Mehlhorn, Kurt, Schirra, Stefan, Alefeld, Götz, Rohn, Jiri, Rump, Siegfried M., Yamamoto, Tetsuro
A Separation Bound for Real Algebraic Expressions (2001)
Burnikel, Christoph, Funke, Stefan, Mehlhorn, Kurt, Schirra, Stefan, Schmitt, Susanne
TSP-Based Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Schirra
An instance of the curve reconstruction problem is a nite sample V of an unknown curve . The task is to connect the points in V in the order in which they lie on . Several new algorithms for the...
Experiments on Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Näher, Stefan Schirra
An instance of the curve reconstruction problem is a finite sample V of an unknown curve gamma...
A strong and easily computable separation bound for arithmetic expressions involving radicals (2000)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We consider arithmetic expressions over operators + , - , * , / , and $\sqrt[k]$ , with integer operands. For an expression E having value $\xi$ , a separation bound sep (E) is a positive real number...
Geometric Computing with CGAL and LEDA (2000)
Mehlhorn, Kurt, Schirra, Stefan, Laurent, Pierre-Jean, Sablonnière, Paul, Schumaker, Larry L.
Experiments on curve reconstruction (2000)
Althaus, Ernst, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan
Edge-Coloring Bipartite Multigraphs in O(E log D) Time (1999)
Richard Cole, Kirstin Ost, Stefan Schirra
Let V , E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be...
Checking geometric programs or verification of geometric structures (1999)
Mehlhorn, Kurt, Näher, Stefan, Seel, Michael, Seidel, Raimund, Schilz, Thomas, Schirra, Stefan, ...
Efficient exact geometric computation made easy (1999)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We show that the combination of the CGAL framework for geometric computation and the number type leda-real yields easy-to-write, correct and efficient geometric programs.
On the Design of CGAL, the Computational Geometry Algorithms Library (1998)
Fabri, Andreas, Giezeman, Geert-Jan, Kettner, Lutz, Schirra, Stefan, Schönherr, Sven
CGAL is a Computational Geometry Algorithms Library written in C++. The goal is to make the large body of geometric algorithms developed inthe field of computational geometry available for industrial...
On the Design of CGAL, the Computational Geometry Algorithms Library (1998)
Fabri, Andreas, Giezeman, Geert-Jan, Kettner, Lutz, Schirra, Stefan, Schönherr, Sven
CGAL is a Computational Geometry Algorithms Library written in C++. The goal is to make the large body of geometric algorithms developed inthe field of computational geometry available for industrial...
On the Design of CGAL, the Computational Geometry Algorithms Library (1998)
Fabri, Andreas, Giezeman, Geert-Jan, Kettner, Lutz, Schirra, Stefan, Schönherr, Sven
CGAL is a Computational Geometry Algorithms Library written in C++. The goal is to make the large body of geometric algorithms developed inthe field of computational geometry available for industrial...
On the design of CGAL a computational geometry algorithms library (1998)
Andreas Fabri, Geert-jan Giezeman, Lutz Kettner, Stefan Schirra, Sven Schönherr
CGAL is a Computational Geometry Algorithms Library written in C++, which is being developed by research groups in Europe and Israel. The goal is to make the large body of geometric algorithms...
Applications of the Generic Programming Paradigm in the Design of CGAL (1998)
Hervé Brönnimann, Lutz Kettner, Stefan Schirra, Remco Veltkamp
We report on the use of the generic programming paradigm in the computational geometry algorithms library cgal. The parameterization of the geometric algorithms in cgal enhances flexibility and...
On the Design of CGAL, the Computational Geometry Algorithms Library (1998)
Andreas Fabri, Andreas Fabri, Geert-jan Giezeman, Geert-jan Giezeman, Lutz Kettner, Lutz Kettner, ...
Cgal is a Computational Geometry Algorithms Library written in C++, which is developed in an Esprit Ltr project. The goal is to make the large body of geometric algorithms developed in the field of...
On the Design of CGAL, the Computational Geometry Algorithms Library (1998)
Geert-jan Giezeman, Lutz Kettner, Sven Schönherr, Unit Inria, Sophia Antipolis, Andreas Fabri, ...
CGAL is a Computational Geometry Algorithms Library written in C++. The goal is to make the large body of geometric algorithms developed in the field of computational geometry available for...
A computational basis for higher-dimensional computational geometry and applications (1998)
Mehlhorn, Kurt, Müller, Michael, Näher, Stefan, Schirra, Stefan, Seel, Michael, Uhrig, Christian, ...
A Computational Basis for Higher-dimensional Computational Geometry and Applications (1997)
Mehlhorn, Kurt, Müller, Michael, Näher, Stefan, Schirra, Stefan, Seel, Michael, Uhrig, Christian, ...
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
Checking geometric programs or verification of geometric structures (1996)
Kurt Mehlhorn, Stefan Naher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, ...
A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program...
The CGAL kernel: A basis for geometric computation (1996)
Andreas Fabri, Geert-jan Giezeman, Lutz Kettner, Stefan Schirra, Sven Schonherr
Only a few of the many algorithms developed over the past two decades in computational geometry found their way into practice. Reasons for this are the dissimilarity
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
Designing a Computational Geometry Algorithms Library (1996)
Introduction Geometric problems arise in many areas. Computer graphics, robotics, manufacturing, and geographic information systems are some examples. Often the same geometric subproblems are to be...
Checking Geometric Programs or Verification of Geometric Structures (1996)
Kurt Mehlhorn Stefan, Stefan Näher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, ...
A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program...
Checking Geometric Programs or Verification of Geometric Structures (1996)
Mehlhorn, Kurt, Näher, Stefan, Schilz, Thomas, Schirra, Stefan, Seel, Michael, Seidel, Raimund, ...
Queries on Voronoi Diagrams of Moving Points (1996)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...
Queries on Voronoi Diagrams of Moving Points (1996)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given n moving postmen described by their motion equations pi(t) = si + vi t, i=1, ... , n, where si belongs to R2 is the position of the i'th postman at time t=0, and vi in R2 is his...
Exact Geometric Computation in LEDA (1995)
Burnikel, Christoph, Könemann, Jochen, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, Uhrig, Christian
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Devillers, Olivier, Golin, Mordecai, Kedem, Klara, Schirra, Stefan
Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i...
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points (1994)
Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, Klara Kedem, ...
Suppose we are given n moving postmen described by their motion equations p i (t) = s i + v i t; i = 1, ..., n, where s i 2 IR 2 is the position of the i'th postman at time t = 0, and v i 2 IR 2...
Revenge of the dog: Queries on Voronoi diagrams of moving points (1994)
Apport De Recherche, Olivier Devillers, Olivier Devillers, Mordecai Golin, Mordecai Golin, Klara Kedem, ...
Suppose we are given n moving postmen described by their motion equations p i #t#=s i + v i t; i =1;:::;n, where s i 2 IR is the position of the i'th postman at time t = 0, and v i 2 IR is his...
How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results (1994)
Burnikel, Christoph, Mehlhorn, Kurt, Schirra, Stefan, Van Leeuwen, Jan
Approximative Bewegungsplanungsverfahren / (1992)
Saarbrücken, Univ., Diss., 1992.
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...