Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Some performance tests of convex hull algorithms
Allison D., Noga M. BIT24 (1):2-13,1984.Type:Article
Date Reviewed: Feb 1 1985

Four two-dimensional convex hull algorithms are explained and experimentally compared in this paper: Graham’s algorithm [1], the first to achieve the O(n log n) optimal worst-case complexity, Jarvis’s “gift-wrapping” algorithm [2], and algorithms of Eddy [3] and of Akl and Toussaint [4], both designed to be fast on uniform distributions of points. Jarvis’s algorithm is much slower than the other three; it is, however, the only one that generalizes to higher dimensions. The Eddy and Akl/Toussaint algorithms are, as expected, the best for uniform distributions. But the most interesting result of this study is that the Graham algorithm is the best overall; it is only slightly outperformed on uniform distributions, and is the clear winner when a large fraction of the given points are on the hull.

Reviewer:  Joseph O’Rourke Review #: CR108716
1) Graham, R. L.An efficient algorithm for determing the convex hull of a finite planar set, Inf. Process. Let. 1 (1972), 132-133.
2) Jarvis, R. A.-9MOn the identification of the convex hull of a finite set of points in a plane, Inf. Process. Lett. 2 (1973), 18-21.
3) Eddy, W. R.A new convex hull algorithm for planar sets, ACM Trans. Math. Soft. 3 (1977), 398-403.
4) Akl, S. G.; and T:OLOUSSAINT, G. I. A fast convex hull algorithm, Inf. Process. Lett. 7 (1978), 219-222.
Bookmark and Share
  Featured Reviewer  
 
Geometrical Problems And Computations (F.2.2 ... )
 
 
Geometric Algorithms, Languages, And Systems (I.3.5 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Geometrical Problems And Computations": Date
A fast voronoi-diagram algorithm with quaternary tree bucketing
Ohya T., Iri M., Murota K. Information Processing Letters 18(4): 227-231, 1984. Type: Article
Jan 1 1985
Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm
Chazelle B. (ed) SIAM Journal on Computing 13(3): 488-507, 1984. Type: Article
Mar 1 1985
An optimal contour algorithm for iso-oriented rectangles
Güting R. Journal of Algorithms 5(3): 303-326, 1984. Type: Article
May 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy