|
|
Publications of the Computational Geometry group of the ISG: All by Author
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
- Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn,
Stefan Näher, Stefan Schirra, and Christian Uhrig.
Approximate Motion Planning and the Complexity of the Boundary of the
Union of Simple Geometric Figures.
Algorithmica, 8(5-6):391-408, 1992.
Conference version in Proceedings of 6th ACM Symposium on Computational
Geometry, 1990.
- Michael Andresen, Heidemarie Bräsel, André
Herms, Marc Mörig, Jan Tusch, Frank Werner, and Per Willenius.
Simulated Annealing
and Genetic Algorithms for Minimizing Mean Flow Time in an Open
Shop.
Mathematical and Computer Modelling, 48(7-8):1279-1293, October
2008.
- Prosenjit Bose,
Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid.
On farthest-point information
in networks.
In Proceedings of the 24th Canadian Conference on Computational
Geometry, pages 199-204, 2012.
- Prosenjit Bose,
Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid.
Optimal data
structures for farthest-point queries in cactus networks.
In Proceedings of the 25th Canadian Conference on Computational
Geometry, 2013.
- Prosenjit Bose, Kai Dannies, Jean-Lou De Carufel, Christoph
Doell, Carsten Grimm, Anil Maheshwari, Stefan Schirra, and Michiel Smid.
Network farthest-point diagrams.
Journal of Computational Geometry, 4(1):182-211, 2013.
- Prosenjit Bose,
Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid.
Optimal data structures for farthest-point queries in cactus networks.
Journal of Graph Algorithms and Applications, 19(1):11-41,
2015.
- Heidemarie Bräsel, Lars Dornheim, Sandra Kutz, Marc
Mörig, and Ivo Rössling.
LiSA -- A Library of Scheduling Algorithms.
Technical Report 34/2003, Otto-von-Guericke-Universität Magdeburg,
Fakultät für Mathematik, 2003.
- Heidemarie Bräsel, André Herms, Marc Mörig,
Thomas Tautenhahn, Jan Tusch, Frank Werner, and Per Willenius.
A Comparison of Heuristics for Mean Flow Time Open Shop
Scheduling.
In Information Control Problems in Manufacturing 2006, A Proceedings
volume from the 12th IFAC International Symposium (INCOM'2006),
volume 3, pages 111-116. Elsevier, December 2006.
- Heidemarie Bräsel, André Herms, Marc Mörig, Thomas
Tautenhahn, Jan Tusch, and Frank Werner.
Heuristic
Constructive Algorithms for Open Shop Scheduling to Minimize
Mean Flow Time.
European Journal of Operations Research, 189(3):856-870,
September 2008.
- Hervè Brönniman, Lutz Kettner, Stefan Schirra, and Remco
Veltkamp.
Applications of the Generic Programming Paradigm in the Design of
CGAL.
Research Report MPI-I-98-1-030, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, December 1998.
- Hervè Brönnimann, Lutz Kettner, Stefan Schirra, and
Remco Veltkamp.
Applications of the Generic Programming Paradigm in the Design of
CGAL.
In M. Jazayeri, R. Loos, and D. Musser, editors, Generic Programming -
Proceedings of a Dagstuhl Seminar, volume 1766 of Lecture Notes
in Computer Science, pages 206-216, Berlin, 2000. Springer-Verlag.
- Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra.
How to Compute the Voronoi Diagram of Line Segments: Theoretical
and Experimental Results.
In Proceedings of the 2nd European Symposium on Algorithms (ESA94),
Arnhem, The Netherlands, pages 227-239, 1994.
- Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra.
On Degeneracy in Geometric Computations.
In Proceedings of the 5th ACM-SIAM Symposium on Discrete
Algorithms, pages 16-23, 1994.
- Christoph Burnikel, Jochen Könemann, Kurt Mehlhorn, Stefan
Näher, Stefan Schirra, and Christian Uhrig.
Exact Geometric Computation in LEDA.
In 11th ACM Symposium on Computational Geometry (SoCG95), Vancouver,
British Columbia, Canada, June, 5th - 7th. acm-Press, New York, 1995.
C18-C19.
- Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra.
The LEDA Class Real Number.
Research Report MPI-I-96-1-001, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, January 1996.
- Christoph Burnikel, Rudolf Fleischer Kurt Mehlhorn, and Stefan
Schirra.
A Strong and Easily Computable Separation Bound for Arithmetic
Expressions Involving Square Roots.
In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms
(SODA97, 1997.
- Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan
Schirra.
Efficient Exact Geometric Computation Made Easy.
In Proc. Annual ACM Symposium on Computional Geometry, Proceedings
of 15th ACM Symposium on Computational Geometry, pages 341-350, 1999.
- Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, and Stefan
Schirra.
A Strong and Easily Computable Separation Bound for Arithmetic
Expressions Involving Radicals.
Algorithmica, 27:87-99, 2000.
- Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra,
and Susanne Schmitt.
A Separation Bound for Real Algebraic Expressions.
In Proceedings of the 9th European Symposium on Algorithms (ESA01),
Arhus, Denmark, volume 2161 of Lecture Notes in Computer
Science, pages 254-265, Berlin, 2001. Springer-Verlag.
- Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra,
and Susanne Schmitt.
A Separation Bound
for Real Algebraic Expressions.
Algorithmica, 55(1):14-28, September 2009.
- R. Cole, K. Ost, and
S. Schirra.
Edge-Coloring Bipartite Multigraphs in O(E log D) Time.
Research Report TR1999-792, New York University, September 1999.
- Richard Cole,
Kirstin Ost, and Stefan Schirra.
Edge-Coloring Bipartite
Multigraphs in O(E log D) Time.
Combinatorica, 21(1):5-12, 2001.
- Marc de Berg,
Marc van Kreveld, and Stefan Schirra.
A new Approach to Subdivision Simplification.
In ACSM/ASPRS Annual Convention & Exposition Technical Papers,
Charlotte, North Carolina, USA, February, pages 79-88, Bethesda,
1995. ACSM, Bethesda.
- Mark de Berg,
Marc van Kreveld, and Stefan Schirra.
Topologically Correct Subdivision Simplification Using the Bandwith
Criterion.
Cartography and Geographic Information Systems, 25:243-257,
1998.
- Jean-Lou
De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, and Michiel Smid.
A note on the unsolvability of the weighted region shortest path problem.
Computational Geometry. Theory and Applications, 47(7):724-727,
2014.
- Olivier Devillers, Mordecai J. Golin, Klara Kedem, and Stefan
Schirra.
Queries on Voronoi Diagrams of Moving Points.
Computational Geometry: Theory and Applications, 6(5):315-327,
September 1996.
- Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra,
and Sven Schönherr.
The CGAL Kernel: A Basis for Geometric Computation.
In Applied Computational Geometry: Towards Geometric Engineering
Proceedings (WACG'96), Philadelphia, May, 27th-28th, pages 191-202,
Berlin, 1996. Springer-Verlag.
- Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra,
and Sven Schönherr.
On the Design of CGAL, the Computational Geometry Algorithms
Library.
Research Report MPI-I-98-1-007, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, February 1998.
- Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra,
and Sven Schönherr.
On the Design of CGAL, a Computational Geometry Algorithms
Library.
Software - Practice and Experience, 30(11):1167-1202, September
2000.
- Carsten Grimm
and Sonia Chiasson.
Survey on the fate of digital footprints after death.
In Workshop on Usable Security. Internet Society, 2014.
- Carsten Grimm.
Efficient farthest-point queries in
two-terminal series-parallel networks.
CoRR, abs/1503.01706, 2015.
- Carsten Grimm.
A lower bound on supporting
predecessor search in k sorted arrays.
CoRR, abs/1507.03823, 2015.
- Paul J.
Heffernan and Stefan Schirra.
Approximate Decision Algorithms for Point Set Congruence.
Computational Geometry: Theory and Applications, 4(3):137-156,
July 1994.
Conference version in Proceedings of the 8th ACM Symposium on Computational
Geometry, 1992.
- Sabine Helwig, Falk
Hüffner, Ivo Rössling, and Maik Weinard.
Chapter 3. Selected
Design Issues.
In Matthias Müller-Hannemann and Stefan Schirra, editors, Algorithm
Engineering, volume 5971 of LNCS, pages 58-126.
Springer, 2010.
- Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and
Chee Yap.
Classroom Examples of Robustness Problems in Geometric
Computations.
In Proceedings of the 12th European Symposium on Algorithms (ESA04),
Bergen, Norway, volume 3221 of Lecture Notes in Computer
Science, pages 702-713, Berlin, 2004. Springer-Verlag.
- Lutz
Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap.
Reply to ''Backward Error Analysis ...''
In Computational Science and Its Applications - ICCSA 2006, International
Conference, Glasgow, UK, May 8-11, 2006, Proceedings, Part I, volume
3980 of LNCS, pages 60-60. Springer, 2006.
- Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and
Chee Yap.
Classroom Examples
of Robustness Problems in Geometric Computation.
Computational Geometry: Theory and Applications, 40(1):61-78, May
2008.
- Kamala Krithivasan, Anna Rema, Stefan Schirra, and P.I.
Vijaykumar.
Velocity
Planning for a Robot Moving Along the Shortest Straight Line
Path Among Moving Obstacles.
In Proceedings of the 8th Canadian Conference on Computational Geometry
(CCCG'96), pages 149-154, Ottawa, August 1996.
- Kurt
Mehlhorn and Stefan Schirra.
Generalized and improved constructive separation bound for real algebraic
expressions.
Research Report MPI-I-2000-1-004, Max-Planck-Institut für Informatik,
Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, November 2000.
- Kurt
Mehlhorn and Stefan Schirra.
Geometric Computing with CGAL and LEDA, pages 277-286.
Vanderbilt University Press, 2000.
- Kurt Mehlhorn, Stefan Näher, Stefan Schirra, Michael Seel,
and Christian Uhrig.
A Computational Basis for Higher-dimensional Computational
Geometry.
Research Report MPI-I-96-1-016, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, May 1996.
- Kurt Mehlhorn, Michael Müller, Stefan Näher, Stefan
Schirra, Michael Seel, Christian Uhrig, and Joachim Ziegler.
A Computational Basis for Higher-dimensional Computational Geometry
and Applications.
Computational Geometry: Theory and Applications, 10(4):289-303,
July 1998.
Conference version in Proceedings of the 13th ACM Symposium on Computational
Geometry, 1997.
- Kurt Mehlhorn, Stefan Näher, Thomas Schilz, Stefan Schirra,
Michael Seel, Raimund Seidel, and Christian Uhrig.
Checking Geometric Programs or Verification of Geometric
Structures.
Computational Geometry: Theory and Applications, 12(1-2):85-103,
February 1999.
Conference version in Proceedings of the 12th ACM Symposium on Computational
Geometry, 1996.
- Marc
Mörig and Stefan Schirra.
On the Design and
Performance of Reliable Geometric Predicates using Error-free
Transformations and Exact Sign of Sum Algorithms.
In Proceedings of the 19th Canadian Conference on Computational Geometry
(CCCG '07), pages 45-48, Carleton University, Ottawa, Canada, August
2007.
- Marc Mörig and
Stefan Schirra.
Engineering
an exact sign of sum algorithm.
Technical Report FIN-002-2010, Otto-von-Guericke-Universität
Magdeburg, Fakultät für Informatik, February 2010.
- Marc Mörig
and Stefan Schirra.
Precision-Driven
Computation in the Evaluation of Expression-Dags with Common Subexpressions:
Problems and Solutions, pages 451-465.
Springer International Publishing, Cham, 2016.
- Marc Mörig and
Silvio Weging.
Summing
expansions exactly and efficiently.
Technical Report FIN-09-2011, Otto-von-Guericke-Universität
Magdeburg, Fakultät für Informatik, November 2011.
- Marc
Mörig, Dieter Rautenbach, Michiel Smid, and Jan Tusch.
An Omega(n log n) lower
bound for computing the sum of even-ranked elements.
Information Processing Letters, 109(16):955-956, July 2009.
- Marc Mörig, Ivo
Rössling, and Stefan Schirra.
On
the design and implementation of a generic number type for real algebraic
number computations based on expression dags.
Technical Report FIN-001-2010, Otto-von-Guericke-Universität
Magdeburg, Fakultät für Informatik, February 2010.
- Marc Mörig, Ivo
Rössling, and Stefan Schirra.
On the design and
implementation of a generic number type for real algebraic number
computations based on expression dags.
Mathematics in Computer Science, 4(4):539-556, 2010.
- Marc Mörig, Sven
Scholz, Tobias Tscheuschner, and Eric Berberich.
Chapter 6.
Implementation Aspects.
In Matthias Müller-Hannemann and Stefan Schirra, editors, Algorithm
Engineering, volume 5971 of LNCS, pages 237-289.
Springer, 2010.
- Marc Mörig.
Modulare Dekomposition durch geordnete Partitionierung der Knotenmenge:
Grundlagen und Implementierung.
Diplomarbeit, Otto-von-Guericke-Universität Magdeburg, April
2006.
- Marc Mörig.
Deferring dag
construction by storing sums of floats speeds-up exact decision computations
based on expression dags.
In 3rd International Congress on Mathematical Software (ICMS
2010), volume 6327 of LNCS, pages 109-120, September
2010.
- Matthias Müller-Hannemann and Stefan Schirra, editors.
Algorithm
Engineering, volume 5971 of LNCS.
Springer, 2010.
- Ivo Rössling.
Sprachtheoretische Untersuchungen zu einer Cilianten-Operation.
Diplomarbeit, Otto-von-Guericke-Universität Magdeburg, 2004.
Betreut durch Prof. Jürgen Dassow.
- Stefan Schirra.
Approximate Decision Algorithms for Approximate Congruence.
Information Processing Letters, 42:29-34, 1992.
- Stefan Schirra.
Moving a Disc Between Polygons - VIDEO.
In Proceedings of the 9th ACM Symposium on Computational Geometry
(SoCG93), San Diego, pages 395-396, 1993.
- Stefan Schirra.
Designing a Computational Geometry Algorithms Library.
Research Report MPI-I-97-1-014, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, July 1997.
- Stefan Schirra.
Precision and Robustness in Geometric Computations.
In Algorithmic Foundations of Geographic Information Systems,
volume 1340 of Lecture Notes in Computer Science, pages
255-287, Berlin, 1997. Springer-Verlag.
- Stefan Schirra.
Parameterized Implementations of Classical Planar Convex Hull
Algorithms and Extreme Point Compuations.
Research Report MPI-I-98-1-003, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, January 1998.
- Stefan Schirra.
Robustness and Precision Issues in Geometric Computation.
Research Report MPI-I-98-1-004, Max-Planck-Institut für Informatik, Im
Stadtwald, D-66123 Saarbrücken, Germany, January 1998.
- Stefan Schirra.
A Case Study on the Cost of Geometric Computing.
In Algorithm Engineering and Experimentation (ALENEX99), volume
1619 of Lecture Notes in Computer Science, pages 156-176,
Berlin, 1999. Springer-Verlag.
- Stefan Schirra.
Robustness and Precision Issues in Geometric
Computation, pages 597-632.
Elsevier, 2000.
- Stefan Schirra.
Exact Computation with leda_real - Theory and Geometric
Applications.
In G. Alefeld, J. Rohn, S. Rump, and T. Yamamoto, editors,
Symbolic-algebraic Methods and Verification Method. Springer
Mathematics, Wien, 2001.
- Stefan Schirra.
A Case Study on the Portability of old CGAL Code.
In 2nd CGAL User Workshop, New York, 2004.
- Stefan Schirra.
Real Numbers and Robustness in Computational Geometry.
In 6th Conference on Real Numbers and Computers, Dagstuhl,
Germany, 2004.
- Stefan Schirra.
Feasibility of the
Exact Geometric Computation Paradigm for Largest Empty Anchored
Cylinder Computation in the Plane.
In Proceedings of the 17th Canadian Conference on Computational Geometry
(CCCG '05), pages 171-174, Windsor, August 2005.
- Stefan Schirra.
How Reliable are Practical Point in Polygon Strategies?
In Proceedings of the 16th European Symposium on Algorithms
(ESA'08), number 5193 in LNCS, pages 744-755, September 2008.
- Stefan Schirra.
Much Ado about
Zero.
In Efficient Algorithms, volume 5760 of LNCS, pages
408-421, September 2009.
- Stefan Schirra.
On the Use of Adaptive, Exact Decisions Number Types Based on Expression-Dags
in Geometric Computing.
In Proc. of the Canadian Conference on Computational Geometry,
pages 412-418, 2014.
- Jörg
Schwerdt, Michiel Smid, and Stefan Schirra.
Computing the Minimum Diameter for Moving Points: An Exact
Implementation using Parametric Search.
In Proceedings of the 13th ACM Symposium on Computational Geometry
(SoCG97), Nice, France, June, 4 - June, 6, pages 466-468, New York,
1997. ACM Press.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen synchroner, deterministischer
Ketten-Code-Bild-Systeme.
Diplomarbeit, Otto-von-Guericke-Universität Magdeburg, 1999.
Betreut durch Prof. Jürgen Dassow.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen synchroner, deterministischer
Ketten-Code-Bild-Systeme.
Technical Report 8/2002, Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, 2002.
- Bianca Truthe.
On the Finiteness of Picture Languages of synchronous, simple
non-deterministic Chain Code Picture Systems.
Fundamenta Informaticae, 56:389-409, 2003.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen synchroner, deterministisch-tabellierter
Ketten-Code-Bild-Systeme.
Technical Report 15/2003, Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, 2003.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen synchroner,
einfach-nichtdeterministischer Ketten-Code-Bild-Systeme.
Technical Report 7/2003, Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, 2003.
- Bianca Truthe.
A Method for Deciding the Finiteness of Deterministic Tabled
Picture Languages.
In Proceedings of the Eighth International Conference on Developments in
Language Theory, Auckland, New Zealand, volume 3340 of Lecture
Notes in Computer Science, pages 406-417, Berlin, December 2004.
Springer-Verlag.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen synchroner, tabellierter
Ketten-Code-Bild-Systeme.
Technical Report 8/2004, Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, 2004.
- Bianca Truthe.
Zur Endlichkeit von Bildsprachen zu tabellierten
Ketten-Code-Bild-Systemen.
In Suna Bensch, Oliver Boldt, Henning Bordihn, and Helmut Jürgensen,
editors, 14. Theorietag Automaten und Formale Sprachen,
volume 2, pages 135-139, Postdam, Germany, 2004. Institut für
Informatik, Universität Potsdam.
- Bianca Truthe.
A Method for Deciding the Finiteness of Synchronous Tabled
Picture Languages.
In Zoltán Esik and Zoltán Fülöp, editors, 11th
International Conference, AFL 2005, pages 292-305, Dobogok�,
Hungary, 17.-20. Mai 2005. Institute of Informatics, University of Szeged,
Hungary.
- Bianca Truthe.
Äquivalenz von Bildsprachen synchroner, deterministischer
Ketten-Code-Bild-Systeme.
In Henning Fernau, editor, 15. Theorietag Automaten und Formale
Sprachen, volume WSI-2005-16, pages 59-62. Universität
Tübingen, 2005.
- Bianca Truthe.
Endlichkeit von Bildsprachen synchroner, kontextfreier
Ketten-Code-Bild-Systeme.
Dissertation, Otto-von-Guericke-Universität Magdeburg, Magdeburg, 2005.
Shaker-Verlag Aachen, ISBN: 3-8322-4223-6.
- Bianca Truthe.
On the Finiteness of Picture Languages of Synchronous Deterministic
Chain Code Picture Systems.
Acta Cybernetica, 17(1):53-73, 2005.
- Bianca Truthe.
The Finiteness of
Synchronous, Tabled Picture Languages is Decidable.
Theoretical Computer Science, 366(3):297-315, November 2006.
- Jan Tusch and
Stefan Schirra.
Experimental Comparison
of the Cost of Approximate and Exact Convex Hull Computation in
the Plane.
In Proceedings of the 18th Canadian Conference on Computational Geometry
(CCCG'06), pages 19-22, 2006.
- Jan Tusch.
Template
little numbers: A toolkit for more userfriendly efficient exact geometric
computation.
Technical Report FIN-003-2010, Otto-von-Guericke-Universität
Magdeburg, Fakultät für Informatik, February 2010.
The publications lists were created with the tool »bib2html« by
David Hull.
|