Another Classroom Example of Robustness Problems in Planar Convex Hull Computation

摘要

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 their work by providing problematic examples for another planar convex hull algorithm.