LIPIcs.SoCG.2019.65.pdf
- Filesize: 3.05 MB
- 2 pages
Document
A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition)
Author
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
Cite AsGet BibTex
Maarten Löffler. A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 65:1-65:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.65
https://doi.org/10.4230/LIPIcs.SoCG.2019.65
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- convex hull
- efficiency
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- A.M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9(5):216-219, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90072-3.
-
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 3rd edition, 2008.
- R.L. Graham. An efficient algorith for determining the convex hull of a finite planar set. Information Processing Letters, 1(4):132-133, 1972. URL: http://dx.doi.org/10.1016/0020-0190(72)90045-2.