Computing convex hull in a floating point arithmetic
Most known algorithms for computation of convex hulls presume exact arithmetic and may be unstable in finite precision arithmetic. A floating point algorithm like \textit{S. Fortune's} [Stable maintenance of point-set triangulations in two dimension, Proceedings 27th IEEE Symposium on Foundations of Computer Science, 494-499 (1989)] gives only approximate hulls that may not be convex. This paper presents an algorithm \({\mathbf{Convex}}\) that is numerically stable and extracts from the output of Fortune's algorithm a truly convex hull; the distances of the new points from the input points are well controlled at linear functions of machine precision \(u\).
scientific article; zbMATH DE number 682493