An efficient and numerically correct algorithm for the 2D convex hull problem (Q919797)

This paper is concerned with the determination of the boundary of the convex hull of a finite set of points in the plane. It presents an algorithm which is based on the algorithm by \textit{S. G. Akl} and \textit{G. T. Toussaint} [Inform. Processing Lett. 7, 219-222 (1978; Zbl 0392.52003)] and the Merge Hull algorithm described by \textit{F. P. Preparata} and \textit{M. I. Shamos} [Computational geometry, an introduction (1985; Zbl 0575.68059)]. Its numerical correctness is ensured by using special routines for interval arithmetic and multiple precision arithmetic. Its worst-case running time behaviour is O(N log N) with a small constant multiplier where N denotes the number of points and it has expected linear time performance for various kinds of input patterns. For many input point patterns it seems to run faster than any currently known plane convex hull algorithms. Theoretically, the algorithm by \textit{D. G. Kirkpatrick} and \textit{R. Seidel} [SIAM J. Comput. 15, 287-299 (1986; Zbl 0589.68035)] with an asymptotical worst-case running behaviour of O(N log h) (where h is the number of the edges of the convex hull) seems to be better, but has not yet been studied practically. Also its expected performance has not been analyzed.