Some performance tests of convex hull algorithms (Q1070524)

The authors test the two-dimensional convex hull algorithms of \textit{R. L. Graham} [Inf. Process. Lett. 1, 132-133 (1972; Zbl 0236.68013)], \textit{R. A. Jarvis} [Inf. Process. Lett. 2, 18-21 (1973; Zbl 0256.68041)], \textit{W. F. Eddy}[ACM Trans. math. Software 3, 398-403 (1977; Zbl 0374.68036)] and \textit{S. G. Akl} and \textit{G. T. Toussaint} [Inf. Process. Lett. 7, 219-222 (1978; Zbl 0392.52003)], by comparing Fortran implementations of them on four different planar point distributions. Several modifications of both the Graham and Jarvis algorithms are considered. The running times obtained by these experiments indicate that the Graham algorithm is the most convenient on point distributions where most of the points are on or near the boundary of the hull, while the Eddy and Akl-Toussaint algorithms are the bests for uniform distributions of points in the plane. The authors suggest that the design of significantly better convex hull algorithms requires the development of a faster sort algorithm.