Some performance tests of convex hull algorithms |
| |
Authors: | D. C. S. Allison M. T. Noga |
| |
Affiliation: | (1) Department of Computer Science, Virginia Polytechnic Institute and State University, 24061 Blacksburg, Virginia, USA |
| |
Abstract: | The two-dimensional convex hull algorithms of Graham, Jarvis, Eddy, and Akl and Toussaint are tested on four different planar point distributions. Some modifications are discussed for both the Graham and Jarvis algorithms. Timings taken of FORTRAN implementations indicate that the Eddy and Akl-Toussaint algorithms are superior on uniform distributions of points in the plane. The Graham algorithm outperforms the others on those distributions where most of the points are on or near the boundary of the hull. |
| |
Keywords: | Convex hull computational geometry sorting distributive partitioning |
本文献已被 SpringerLink 等数据库收录! |