Conference and journal publications
Research reports
Companion pages to papers describing experimental work


Conference and journal publications

How Reliable are Practical Point in Polygon Strategies?
Stefan Schirra
Proceedings of the 16th European Symposium on Algorithms (ESA08), Karlsruhe, Germany, 2008, LNCS 5193, pages 744-755.

A Separation Bound for Real Algebraic Expressions
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Algorithmica
Conference version in Proceedings of the 9th European Symposium on Algorithms (ESA01), Arhus, Denmark, 2001, LNCS 2161, pages 254-265.

Classroom Examples of Robustness Problems in Geometric Computations
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
Computational Geometry: Theory and Applications 40(1):61-78, 2008
Conference version in Proceedings of the 12th European Symposium on Algorithms (ESA04), Bergen, Norway, 2004, LNCS 3221, pages 702-713.

On the Design and Performance of Reliable Geometric Predicates using Error-free Transformations and Exact Sign of Sum Algorithms
Marc Mörig, Stefan Schirra
19th Canadian Conference on Computational Geometry (CCCG 07), 2007, pages 45-48.

Experimental Comparison of the Cost of Approximate and Exact Convex Hull Computation in the Plane
Stefan Schirra, Jan Tusch
18th Canadian Conference on Computational Geometry (CCCG 06), 2006.

Feasibility of the Exact Geometric Computation Paradigm for Largest Empty Anchored Cylinder Computation in the Plane
Stefan Schirra
17th Canadian Conference on Computational Geometry (CCCG 05), 2005.

Real Numbers and Robustness in Computational Geometry
Stefan Schirra
6th Conference on Real Numbers and Computers, Dagstuhl, Germany, 2004.

A Case Study on the Portability of old CGAL Code
Stefan Schirra, Christian Schulz
2nd CGAL User Workshop, New York, 2004.

Edge-Coloring Bipartite Multigraphs in O(E log D) Time
Richard Cole, Kirstin Ost, Stefan Schirra
Combinatorica 21(1):5-12, 2001

Exact Computation with leda_real - Theory and Geometric Applications
In G. Alefeld, J. Rohn, S. Rump, T. Yamamoto Ed., Symbolic-algebraic Methods and Verification Methods
Springer Mathematics, Wien 2001.

Applications of the Generic Programming Paradigm in the Design of CGAL
Herve Brönnimann, Lutz Kettner, Stefan Schirra and Remco Veltkamp
In M. Jazayeri, R. Loos, D. Musser Ed., Generic Programming - Proceedings of a Dagstuhl Seminar, LNCS 1766, Springer Berlin, 2000, pages 206-216.

On the Design of CGAL, a Computational Geometry Algorithms Library
Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr
Software - Practice and Experience 30:1167-1202, September 2000

A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals
Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra
Algorithmica 27:87-99, 2000

Robustness and Precision Issues in Geometric Computation
Stefan Schirra
Handbook of Computational Geometry, Elsevier, 2000, pages 597-632

Geometric Computing with CGAL and LEDA
Kurt Mehlhorn and Stefan Schirra
Curves and Surface Design: St. Malo 1999, Vanderbilt University Press, 2000, pages 277-286

Efficient Exact Geometric Computation Made Easy
Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra
Proceedings of 15th ACM Symposium on Computational Geometry, 1999, pages 341-350

Checking Geometric Programs or Verification of Geometric Structures
Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra, Michael Seel, Raimund Seidel, and Christian Uhrig
Computational Geometry: Theory and Applications 12:85-103, 1999
Conference version in Proceedings of the 12th ACM Symposium on Computational Geometry, 1996

A Case Study on the Cost of Geometric Computing
Stefan Schirra
Algorithm Engineering and Experimentation (ALENEX99), LNCS 1619, Springer, Berlin, 1999, pages 156-176

Topologically Correct Subdivision Simplification Using the Bandwith Criterion
Mark de Berg, Marc van Kreveld, and Stefan Schirra
Cartography and Geographic Information Systems 25:243-257, 1998

A Computational Basis for Higher-dimensional Computational Geometry and Applications
Kurt Mehlhorn, Michael Müller, Stefan Näher, Stefan Schirra, Michael Seel, Christian Uhrig, and Joachim Ziegler
Computational Geometry: Theory and Applications 10:289-303, 1998
Conference version in Proceedings of the 13th ACM Symposium on Computational Geometry, 1997

Precision and Robustness in Geometric Computations
Stefan Schirra
In: Algorithmic Foundations of Geographic Information Systems, LNCS 1340, Springer, Berlin, 1997, pages 255-287

Computing the Minimum Diameter for Moving Points: An Exact Implementation using Parametric Search
Jörg Schwerdt, Michiel Smid, and Stefan Schirra
In: Proceedings of the 13th ACM Symposium on Computational Geometry (SoCG97), Nice, France, June, 4 - June, 6, ACM Press, New York, 1997, pages 466-468

A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Square Roots
Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan Schirra
In: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA97), 1997

Queries on Voronoi Diagrams of Moving Points
Olivier Devillers, Mordecai J. Golin, Klara Kedem, and Stefan Schirra
Computational Geometry: Theory and Applications 6:315-327, 1996
Conference version in Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

The CGAL Kernel: A Basis for Geometric Computation
Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr
In: Applied Computational Geometry: Towards Geometric Engineering Proceedings (WACG'96), Philadelphia, May, 27th-28th, Springer, Berlin, 1996, pages 191-202

Velocity planning for a robot moving along the shortest straight line path among moving obstacles
Kamala Krithivasan, Anna Rema, Stefan Schirra, and P.I. Vijaykumar
In: Canadian Conference on Computational Geometry (CCCG '96), Ottawa, Canada, August 12th-15th, Carleton University Press, Ottawa, 1996, pages 149-154

A new approach to subdivision simplification
Marc de Berg, Marc van Kreveld, and Stefan Schirra
In: ACSM/ASPRS Annual Convention & Exposition Technical Papers, Charlotte, North Carolina, USA, February, ACSM, Bethesda, 1995, pages 79-88

Exact Geometric Computation in LEDA
Christoph Burnikel, Jochen Könemann, Kurt Mehlhorn, Stefan Näher, Stefan Schirra, and Christian Uhrig
In: 11th ACM Symposium on Computational Geometry (SoCG95), Vancouver, British Columbia, Canada, June, 5th - 7th, acm-Press, New York, 1995, C18-C19

On degeneracy in geometric computations
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, 1994, pages 16-23

How to compute the Voronoi diagram of line segments: Theoretical and experimental results
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
In: Proceedings of the 2nd European Symposium on Algorithms (ESA94), Arnhem, The Netherlands, 1994, pages 227-239

Approximate decision algorithms for point set congruence
Paul J. Heffernan and Stefan Schirra
Computational Geometry: Theory and Applications 4:137-156, 1994
Conference version in Proceedings of the 8th ACM Symposium on Computational Geometry, 1992

Moving a disc between polygons - VIDEO
Stefan Schirra
In: Proceedings of the 9th ACM Symposium on Computational Geometry (SoCG93), San Diego, 1993, pages 395-396

Approximate decision algorithms for approximate congruence
Stefan Schirra
Information Processing Letters 43:29-34, 1992

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Näher, Stefan Schirra, and Christian Uhrig
Algorithmica 8:391-408, 1992
Conference version in Proceedings of 6th ACM Symposium on Computational Geometry, 1990


Research Reports


MPI-I-2000-1-004
A Generalized and Improved Constructive Separation Bound for Real Algebraic Expressions
Kurt Mehlhorn and Stefan Schirra

NYU-TR1999-792
Edge-Coloring Bipartite Multigraphs in O(E log D) Time
Richard Cole, Kirstin Ost, Stefan Schirra

MPI-I-98-1-030
Applications of the Generic Programming Paradigm in the Design of CGAL
Hervé Brönniman, Lutz Kettner, Stefan Schirra, Remco Veltkamp

MPI-I-98-1-007
On the Design of CGAL, the Computational Geometry Algorithms Library
Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra and Sven Schönherr

MPI-I-98-1-004
Robustness and Precision Issues in Geometric Computation
Stefan Schirra

MPI-I-98-1-003
Parameterized Implementations of Classical Planar Convex Hull Algorithms and Extreme Point Compuations
Stefan Schirra

MPI-I-97-1-014
Designing a Computational Geometry Algorithms Library
Stefan Schirra

MPI-I-96-1-016
A Computational Basis for Higher-dimensional Computational Geometry
Kurt Mehlhorn, Stefan Näher, Stefan Schirra, Michael Seel, and Christian Uhrig

MPI-I-96-1-001
The LEDA class real number
Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra

MPI-I-94-150
On Characteristic Points and Approximate Decision Algorithms for the Minimum Hausdorff Distance
L. Paul Chew, Klara Kedem, and Stefan Schirra

MPI-I-94-149
Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points
Olivier Devillers, Mordecai Golin, Stefan Schirra, and Klara Kedem

MPI-I-91-110
Approximate Decision Algorithms for Point Set Congruence
Paul J. Heffernan and Stefan Schirra


Companion pages to papers describing experimental work

Companion pages to How Reliable are Practical Point in Polygon Strategies?

Companion pages to A Separation Bound for Real Algebraic Expressions

Companion pages to Efficient Exact Geometric Computation Made Easy

Companion pages to A Case Study on the Cost of Geometric Computing