A manual comparison of convex hull algorithms

We have verified experimentally that there is at least one point set on which Andrew's algorithm (based on Graham's scan) to compute the convex hull of a set of points in the plane is significantly faster than a brute-force approach, thus supporting existing theoretical analysis with practical evidence. Specifically, we determined that executing Andrew's algorithm on the point set P = (1,4), (2,8), (3,10), (4,1), (5,7), (6,3), (7,9), (8,5), (9,2), (10,6) takes 41 minutes and 18 seconds; the brute-force approach takes 3 hours, 49 minutes, and 5 seconds.

keywords: Computational Geometry, Convex Hulls, UP

Workshop or Poster (weakly reviewed)

Maarten Lรถffler
A manual comparison of convex hull algorithms
Proc. 34th Symposium on Computational Geometry
, 2019
https://drops.dagstuhl.de/opus/volltexte/2019/10469/

back to list