{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,15]],"date-time":"2026-11-15T06:14:25Z","timestamp":1794723265472,"version":"4.9.1"},"reference-count":54,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T00:00:00Z","timestamp":1543363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: plane-sweep, torch, quickhull, and throw-away. With a new set of space-efficient implementations, the experimental results\u2014in the integer-arithmetic setting\u2014are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.<\/jats:p>","DOI":"10.3390\/a11120195","type":"journal-article","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T11:43:44Z","timestamp":1543405424000},"page":"195","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Convex-Hull Algorithms: Implementation, Testing, and Experimentation"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2839-166X","authenticated-orcid":false,"given":"Ask Neve","family":"Gamby","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen East, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7714-5588","authenticated-orcid":false,"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen East, Denmark"},{"name":"Jyrki Katajainen and Company, 3390 Hundested, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,11,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zobel, J. (2014). Writing for Computer Science, Springer. [3rd ed.].","DOI":"10.1007\/978-1-4471-6639-9"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.cad.2015.07.013","article-title":"A total order heuristic-based convex hull algorithm for points in the plane","volume":"70","author":"Gomes","year":"2016","journal-title":"Comput. Aided Des."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0020-0190(79)90072-3","article-title":"Another efficient algorithm for convex hulls in two dimensions","volume":"9","author":"Andrew","year":"1979","journal-title":"Inf. Process. Lett."},{"key":"ref_4","unstructured":"Gomes, A.J.P. (2018, October 02). Git Repository. Available online: https:\/\/github.com\/mosqueteer\/TORCH\/."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","article-title":"An efficient algorithm for determining the convex hull of a finite planar set","volume":"1","author":"Graham","year":"1972","journal-title":"Inf. Process. Lett."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","article-title":"On the identification of the convex hull of a finite set of points in the plane","volume":"2","author":"Jarvis","year":"1973","journal-title":"Inf. Process. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02712873","article-title":"Optimal output-sensitive convex hull algorithms in two and three dimensions","volume":"16","author":"Chan","year":"1996","journal-title":"Discrete Comput. Geom."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1145\/355759.355766","article-title":"A new convex hull algorithm for planar sets","volume":"3","author":"Eddy","year":"1977","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0020-0190(78)90021-2","article-title":"Convex hull of a finite set of points in two dimensions","volume":"7","author":"Bykat","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1093\/comjnl\/22.3.262","article-title":"Constructing the convex hull of a set of points in the plane","volume":"22","author":"Green","year":"1979","journal-title":"Comput. J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(78)90003-0","article-title":"A fast convex hull algorithm","volume":"7","author":"Akl","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02237955","article-title":"A note on linear expected time algorithms for finding convex hulls","volume":"26","author":"Devroye","year":"1981","journal-title":"Computing"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"McGeorg, C.C. (2012). A Guide to Experimental Algorithmics, Cambridge University Press.","DOI":"10.1017\/CBO9780511843747"},{"key":"ref_14","first-page":"536","article-title":"On the average number of maxima in a set of vectors and applications","volume":"25","author":"Bentley","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.tcs.2003.05.004","article-title":"Space-efficient planar convex hull algorithms","volume":"321","author":"Iacono","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","article-title":"Quicksort","volume":"5","author":"Hoare","year":"1962","journal-title":"Comput. J."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.comgeo.2007.06.003","article-title":"Classroom examples of robustness problems in geometric computations","volume":"40","author":"Kettner","year":"2008","journal-title":"Comput. Geom."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0262-8856(83)90065-3","article-title":"Time- and storage-efficient implementation of an optimal planar convex hull algorithm","volume":"1","author":"Bhattacharya","year":"1983","journal-title":"Image Vis. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0167-8655(85)90039-X","article-title":"On the ultimate convex hull algorithm in practice","volume":"3","author":"McQueen","year":"1985","journal-title":"Pattern Recognit. Lett."},{"key":"ref_20","unstructured":"Warren, H.S. (2012). Hacker\u2019s Delight, Addison-Wesley Professional. [2nd ed.]."},{"key":"ref_21","unstructured":"Katajainen, J. (2017). Pure Compile-Time Functions and Classes in the CPH MPL, Department of Computer Science, University of Copenhagen. Available online: http:\/\/hjemmesider.diku.dk\/~jyrki\/Myris\/Kat2017R.html."},{"key":"ref_22","unstructured":"Katajainen, J. (2018). Class templates Z<b> and N<b> for fixed-precision arithmetic, work in progress."},{"key":"ref_23","unstructured":"Sack, J.-R., and Urrutia, J. (2000). Robustness and precision issues in geometric computation. Handbook of Computational Geometry, Elsevier."},{"key":"ref_24","first-page":"181","article-title":"Presenting data from experiments in algorithmics","volume":"Volume 2547","author":"Fleischer","year":"2002","journal-title":"Experimental Algorithmics\u2014From Algorithm Design to Robust and Efficient Software"},{"key":"ref_25","unstructured":"GeeksforGeeks (2018, October 02). Convex Hull \u2223 Set 2 (Graham Scan). Available online: http:\/\/www.cdn.geeksforgeeks.org\/convex-hull-set-2-graham-scan\/."},{"key":"ref_26","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","article-title":"Introspective sorting and selection algorithms","volume":"27","author":"Musser","year":"1997","journal-title":"Softw. Pract. Exp."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934510","article-title":"Some performance tests of convex hull algorithms","volume":"24","author":"Allison","year":"1984","journal-title":"BIT Numer. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1006\/jagm.1997.0869","article-title":"On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm","volume":"25","author":"Bhattacharya","year":"1997","journal-title":"J. Algorithms"},{"key":"ref_30","unstructured":"Chan, T.M.Y., Snoeyink, J., and Yap, C.K. (1995, January 22\u201324). Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","article-title":"The ultimate planar convex hull algorithm?","volume":"15","author":"Kirkpatrick","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/BF02523195","article-title":"Randomized quickhull","volume":"17","author":"Wenger","year":"1997","journal-title":"Algorithmica"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1109\/T-C.1972.223507","article-title":"Measuring concavity on a rectangular mosaic","volume":"C-21","author":"Sklansky","year":"1972","journal-title":"IEEE Trans. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/BF01994842","article-title":"Stable minimum space partitioning in linear time","volume":"32","author":"Katajainen","year":"1992","journal-title":"BIT Numer. Math."},{"key":"ref_35","unstructured":"Lipton, R.J. (2018, November 27). Galactic Algorithms. Available online: https:\/\/rjlipton.wordpress.com\/2010\/10\/23\/galactic-algorithms\/."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232: Heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0020-0255(84)90025-2","article-title":"On the definition and computation of rectilinear convex hulls","volume":"33","author":"Ottmann","year":"1984","journal-title":"Inf. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(80)90036-8","article-title":"A note on finding convex hulls via maximal vectors","volume":"11","author":"Devroye","year":"1980","journal-title":"Inf. Process. Lett."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/BF01188711","article-title":"Fast linear expected-time algorithms for computing maxima and convex hulls","volume":"9","author":"Bentley","year":"1993","journal-title":"Algorithmica"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-319-38851-9_12","article-title":"Worst-case-efficient dynamic arrays in practice","volume":"Volume 9685","author":"Goldberg","year":"2016","journal-title":"Proceedings of the 15th International Symposium on Experimental Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/235815.235821","article-title":"The Quickhull algorithm for convex hulls","volume":"22","author":"Barber","year":"1996","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_42","unstructured":"Barber, C.B. (2018, October 02). Qhull Manual. Available online: http:\/\/www.qhull.org\/."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/365660.365678","article-title":"Algorithm 271: Quickersort","volume":"8","author":"Scowen","year":"1965","journal-title":"Commun. ACM"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(80)90142-8","article-title":"Further comments on Bykat\u2019s convex hull algorithm","volume":"10","author":"Overmars","year":"1980","journal-title":"Inf. Process. Lett."},{"key":"ref_45","unstructured":"Shewchuk, J.R. (2018, November 27). Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry. Available online: http:\/\/www.cs.cmu.edu\/~quake\/robust.html."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10543-015-0574-9","article-title":"Simple floating-point filters for the two-dimensional orientation problem","volume":"56","author":"Ozaki","year":"2016","journal-title":"BIT Numer. Math."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1145\/231731.231735","article-title":"Static analysis yields efficient exact integer arithmetic for computational geometry","volume":"15","author":"Fortune","year":"1996","journal-title":"ACM Trans. Graph."},{"key":"ref_48","unstructured":"gmplib.org (2018, November 27). GMP: The GNU Multiple Precision Arithmetic Library. Available online: https:\/\/gmplib.org\/."},{"key":"ref_49","unstructured":"Gamby, A.N., and Katajainen, J. (2018). Convex-Hull Algorithms in C++, Department of Computer Science, University of Copenhagen. Available online: http:\/\/hjemmesider.diku.dk\/~jyrki\/Myris\/GK2018S.html."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10013-014-0067-1","article-title":"Quicker than Quickhull","volume":"43","author":"Hoang","year":"2015","journal-title":"Vietnam J. Math."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Gamby, A.N., and Katajainen, J. (2018). A faster convex-hull algorithm via bucketing, work in progress.","DOI":"10.1007\/978-3-030-34029-2_30"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Devroye, L. (1986). Lecture Notes on Bucket Algorithms, Birkh\u00e4user.","DOI":"10.1007\/978-1-4899-3531-1"},{"key":"ref_53","unstructured":"N\u00e4her, S., and Schmitt, D. (2008, January 13\u201315). A framework for multi-core implementations of divide and conquer algorithms and its application to the convex hull problem. Proceedings of the 20th Annual Canadian Conference on Computational Geometry, Montreal, QC, Canada."},{"key":"ref_54","unstructured":"Gamby, A.N., and Katajainen, J. (2017). A Note on the Implementation Quality of a Convex-Hull Algorithm, Department of Computer Science, University of Copenhagen. Available online: http:\/\/hjemmesider.diku.dk\/~jyrki\/Myris\/GK2017R.html."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/12\/195\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:33:11Z","timestamp":1760196791000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/12\/195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,28]]},"references-count":54,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2018,12]]}},"alternative-id":["a11120195"],"URL":"https:\/\/doi.org\/10.3390\/a11120195","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,28]]}}}