Another Classroom Example of Robustness Problems in Planar Convex Hull Computation

Marc Mörig

These are companion pages to "Another Classroom Example of Robustness Problems in Planar Convex Hull Computation", presented at MACIS 2015.

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. [1] provide examples where rounding errors let such straightforward implementations of incremental convex hull computation crash, loop forever, or silently compute garbage. We complement their work by providing problematic examples for another planar convex hull algorithm.

We provide input data and an implementation of the convex algorithm that lets you reproduce and examine the described failures yourself. The package also contains a robust implementation of the algorithm. Furthermore we provide slides that illustrate how the algorithm works followed by an illustration of the two failures.

Download

• another_classroom_example_slides.pdf
  Contains an illustration of the algorithm followed by an illustration of the two failures.
• another_classroom_example.zip
  Source code and input data demonstrating two failures of a simple O(n log n) planar convex hull algorithm.
• another_classroom_example.pdf
  Preliminary version of our paper.

Further Reading

[1]	Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee-Keng Yap. Classroom examples of robustness problems in geometric computation. Computational Geometry: Theory and Applications, 40(1):61-78, May 2008. Companion websites at https://people.mpi-inf.mpg.de/~kettner/proj/NonRobust/index.html
[2]	Marc Mörig. Another Classroom Example of Robustness Problems in Planar Convex Hull Computation. presented at MACIS 2015