MACIS 2015 Session (SS10): Algorithm Engineering in Geometric Computing

MACIS 2015: Home, Sessions Page

Organizer

Rudolf Fleischer (German University of Technology in Oman, Muscat, Oman)
Stefan Schirra (Otto von Guericke University Magdeburg, Germany)

Aim and Scope

While plenty of asymptotically efficient and theoretically optimal algorithms have been designed in computing science, many of these solutions are impractical. In computational geometry the gap is widened by unrealistic assumptions made in theory: exact real arithmetic and input data in general position. The goal of algorithm engineering is to bridge this gap between theory and practice.

Topics (including, but not limited to)

Implementation of computational geometry algorithms
Precision and robustness issues in geometric computing
Exact decisions geometric computation
Software number types in geometric computing

Publications

A short abstract will appear on the conference web page as soon as accepted,
and a post-conference proceedings will be published by LNCS.
Several special issues of the journal Mathematics in Computer Science, published by Birkhäuser/Springer, will be organized after the conference by session organizers. REGULAR (not SHORT) papers would be considered for these special issues.

Submission Guidelines

If you would like to give a talk at MACIS, you need to submit at least a SHORT paper -- see guideline for the details.
The (new) deadline for all submissions is Sep 1, 2015 -- see the Call for Papers for the details
After the meeting, the submission guideline for a journal special issue will be communicated to you by the session organizers.

Talks/Abstracts

Another Classroom Example of Robustness Problems in Planar Convex Hull Computation (PDF)
Marc Mörig (Otto von Guericke University Magdeburg, Germany)

Abstract: Algorithms in computational geometry are designed under the assumption of exact real arithmetic. Indiscriminately replacing exact real arithmetic by hardware floating-point arithmetic almost inevitably leads to robustness problems. Kettner et al. provide examples where rounding errors let such straightforward implementations of incremental convex hull computation crash, loop forever, or silently compute garbage. We complement there work by providing problematic examples for another planar convex hull algorithm.