Prof. Schirra

Prof. Dr. rer. nat. habil. Stefan Schirra

Fakultät für Informatik (FIN)
Institut für Simulation und Graphik (ISG)
Universitätsplatz 2, 39106 Magdeburg, G29-219
Projekte

Abgeschlossene Projekte

Geometrisches Runden und Vereinfachen und Grundlagen exakten geometrischen Rechnens mit algebraischen Zahlen
Laufzeit: 01.05.2006 bis 30.04.2008

Exaktes geometrisches Rechnen ist eine innovative Vorgehensweise, rundungsfehlerbedingte Robustheitsprobleme bei der Implementierung von geometrischen Algorithmen nachhaltig zu vermeiden. Im Gegensatz zum gewöhnlichen Rechnen mit Gleitkommaarithmetik garantiert dieser Ansatz, dass alle Entscheidungen im Programmablauf korrekt getroffen werden. Der Ansatz hat allerdings seinen Preis. Der Implementierungsaufwand ist sehr hoch und die Programme sind im Vergleich zu Gleitkomma-Implementierungen langsamer und benötigen mehr Speicherplatz. Darüberhinaus sind die Resultate oft in den in der Praxis verwendeten Formaten nicht exakt darstellbar und müssen deshalb vereinfacht oder gerundet werden. In unserem Projekt werden algebraische und numerische Grundlagen des exakten geometrischen Rechnens und Rundens weitergehend untersucht und wiederverwendbare Software mit verbesserter Performanz entwickelt.

Projekt im Forschungsportal ansehen

Publikationen

2020

Refining expression DAGs in exact-decisions number types

Wilhelm, Martin; Schirra, Stefan

In: Magdeburg, Dissertation Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik 2020, 179 Seiten [Literaturverzeichnis: Seite 163-176][Literaturverzeichnis: Seite 163-176]

2017

Minimizing the continuous diameter when augmenting a tree with a shortcut

Carufel, Jean-Lou; Grimm, Carsten; Schirra, Stefan; Smid, Michiel

In: Algorithms and Data Structures - Cham : Springer . - 2017, S. 301-312 - (Lecture Notes in Computer Science; 10389) [Symposium: 15th International Symposium, WADS 2017, St. Johns, NL, Canada, July 31 - August 2, 2017]

On interval methods with zero rewriting and exact geometric computation

Schirra, Stefan; Wilhelm, Martin

In: Mathematical Aspects of Computer and Information Sciences - Cham : Springer . - 2017, S. 211-226 - (Lecture Notes in Computer Science; 10693) [Konferenz: 7th International Conferenceon Mathematical Aspects of Computer and Information Sciences, MACIS 2017, Vienna, Austria, November 15-17, 2017]

2016

Precision-driven computation in the evaluation of expression-dags with common subexpressions - problems and solutions

Mörig, Marc; Schirra, Stefan

In: Mathematical Aspects of Computer and Information Sciences - Cham : Springer . - 2016, S. 451-465 - (Lecture Notes in Computer Science; 9582) [Kongress: 6th International Conference Mathematical Aspects of Computer and Information Sciences, MACIS 2015, Berlin, Germany, November 11-13, 2015]

2015

Algorithm engineering for expression dag based number types

Mörig, Marc Andreas; Schirra, Stefan

In: Magdeburg, Univ., Fak. für Informatik, Diss., 2015, V, 183 S.

2014

On the use of adaptive, exact decisions number types based on expression-dags in geometric computing

Schirra, Stefan

In: 26th Canadian Conference on Computational Geometry: Halifax, Nova Scotia, August 11-13, 2014, S. 412-418

2013

Network farthest-point diagrams

Bose, Prosenjit; Dannies, Kai; Carufel, Jean-Lou De; Doell, Christoph; Grimm, Carsten; Maheshwari, Anil; Schirra, Stefan; Smid, Michiel

In: De.arxiv.org - [S.l.]: Arxiv.org, 1991 . - 2013, insges. 26 S.

2011

On design and implementation of a generic number type for real algebraic number computations based on expression dags

Mörig, Marc; Rössling, Ivo; Schirra, Stefan

In: Mathematics in computer science. - Basel : Birkhäuser, Bd. 4.2011, 4, S. 539-556

2010

Algorithm engineering - bridging the gap between algorithm theory and practice

Müller-Hannemann, Matthias; Schirra, Stefan

In: Heidelberg [u.a.]: Springer, 2010, XVI, 513 S. - (Lecture Notes in Computer Science; Theoretical Computer Science and General Issues; 5971; Tutorial; Tutorial), ISBN: 978-3-642-14865-1 [Literaturverz. S. [454] - 496]

Chapter 10. Challenges in algorithm engineering

Müller-Hannemann, Matthias; Schirra, Stefan

In: Algorithm engineering . - Berlin [u.a.] : Springer, ISBN 3-642-14865-4, S. 446-453; Lecture notes in computer science; 5971

Chapter 1. Foundations of algorithm engineering

Müller-Hannemann, Matthias; Schirra, Stefan

In: Algorithm engineering . - Berlin [u.a.] : Springer, ISBN 3-642-14865-4, S. 1-15; Lecture notes in computer science; 5971

2009

Much ado about zero

Schirra, Stefan

In: Efficient algorithms: essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday / Susanne Albers; Helmut Alt; Stefan Näher (eds.): essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday - Berlin [u.a.]: Springer, 2009 . - 2009, S. 408-421 - (Lecture notes in computer science; 5760)Kongress: Colloquium in honor of Kurt Mehlhorn (Saarbrücken : 2009.08.27-28)

2008

Classroom examples of robustness problems in geometric computations

Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee

In: Computational geometry . - Amsterdam : Elsevier, Bd. 40.2008, 1, S. 61-78

How reliable are practical point-in-polygon strategies?

Schirra, Stefan

In: Algorithms - ESA 2008 . - Berlin [u.a.] : Springer, ISBN 3-540-87743-6, S. 744-755; Lecture notes in computer science; 5193Kongress: ESA; 16 (Karlsruhe) : 2008.09.15-17

2007

On the design and performance of reliable geometric predicates using error-free transformations and exact sign of sum algorithms

Mörig, Marc; Schirra, Stefan

In: Proceedings of the 19th Canadian Conference on Computational Geometry, CCCG 2007: August 20-22, 2007, Carleton University, Ottawa, Canada - Ottawa: Prosenjit Bose . - 2007, S. 45-48Kongress: CCCG 2007 19 (Ottawa : 2007.08.20-22)

2006

Experimental comparison of the cost of approximate and exact convex hull computation in the plane

Schirra, Stefan; Tusch, Jan

In: Proceedings of the 18th Canadian Conference on Computational Geometry: August 14-16, 2006 Kingston, Ontario, Canada - Kingston, ON: Queen's Univ. . - 2006, S. 19-22Kongress: CCCG 18 (Kingston, Ontario : 2006.08.14-16)

2004

Classroom examples of robustness problems in geometric computations.

Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvian; Schirra, Stefan; Yap, Chee

In: Albers, Susanne (Hrsg.) ; Radzik, Tomasz (Hrsg.): Algorithms, ESA 2004 (12th annual European symposium Bergen, Norway, September 14 - 17 2004). - proceedings. Berlin : Springer, 2004, S. 702 - 713 (Lecture notes in computer science 3221) . - ESA 2004

Invited lecture : real numbers and robustness in computational geometry.

Schirra, Stefan

In: Frougny, Christiane (Hrsg.) ; ... (Hrsg.): Real numbers and computers, RNCï6 (6th conference Dagstuhl, Germany November 15 - 17 2004). Trier : Univ., 2004, S. 7 - 21 (Trierer Forschungsberichte 04-8)

Kooperationen
  • Carleton University, Ottawa, Kanada, Prof. Dr. Michiel Smid
Profil
Research Interests
  • Algorithms and Data Structures
  • Computational Geometry
  • Exact (Geometric) Computation
  • Motion Planning
  • Computer Graphics
  • Generic Programming
Service
Unabhängige Forschung und Lehre auf den Gebieten
  • Algorithmik
  • Algorithm Engineering
  • Verlässliches geometrisches Rechnen
Vita

Prof. Dr. Stefan Schirra, Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg

Academic titles: Dr. rer. nat. habil.

Place of birth: Saarlouis; Date of birth: 12.08.1961

Professional Data:

1982 - 1988

Study of Computer Science (and Mathematics) at Saarland University

1988

Diplom in Computer Science

1989 - 1991

Research Associate at Saarland University

1991 - 2000

Research Associate at Max Planck Institute for Computer Science

1992

PhD in Computer Science at the Technical Faculty of Saarland University

1999

Habilitation at Saarland University

2000 - 2002

think & solve Beratungsgesellschaft (IT Consulting), Saarbrücken

since   2002

Professor (C3) for Theoretical Computer Science and Computational Geometry at the department for
                      Simulation and Graphics at the Faculty for Computer Science of the Otto von Guericke University
                      Magdeburg

Presse
Algorithmen, das sind Vorgehensvorschriften zur Lösung eines Problems, sind in der Computerwelt allgegenwärtig. Die Suche nach effizienten, d.h. Ressourcen schonenden Algorithmen ist ein zentrales Thema der Informatik. Gegenstand unserer Forschung sind grundlegende geometrische Algorithmen und Algorithmen für diskrete Strukturen. Dabei interessieren wir uns nicht nur für die wichtigen theoretischen Grundlagen solcher Verfahren, sondern auch für das sogenannte Algorithm Engineering und hierbei besonders für den Transfer des Wissens aus der Algorithmischen Geometrie in wiederverwendbare, verlässliche Software.

Letzte Änderung: 08.06.2023 - Ansprechpartner: Webmaster