# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
###### Abstract  
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--in the integer-arithmetic setting--are 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.  
computational geometry; algorithm; convex hull; rectilinear convex hull; algorithm engineering; implementation; testing; experimentation; robustness; performance +
Footnote †: journal:  
1. The algorithm--as it was presented in [2]--was incorrect.
2. The implementation given in [4] was not reliable--calculations could overflow and degenerate inputs were not handled correctly.
3. The implementation required too much memory to be used when the size of the problem reached that of the main memory of the computer.
4. The source code of the competing implementations was not made publicly available so we had to implement them ourselves.
5. Not enough details were provided on the experiments so that we could reproduce them.  
We built this paper around the same algorithms as [PERSON] [2]: rotational-sweep([PERSON]'s scan) [5], gift-wrapping([PERSON] march) [6], [PERSON]'s output-sensitive algorithm [7], plane-sweep([PERSON]'s monotone-chain algorithm) [3], torch[2], and quickhull[8; 9; 10]. Moreover, we examined some heuristics (poles-first[11] and throw-away[12]) that are often used as a preprocessing step to speed up the standard algorithms.  
As advised in ([13], Section 2.3), we divided this study into two parts: (1) In a less formal _pilot study_, our goal was to eliminate unpromising avenues of research. (2) In a more carefully designed _workhorse study_, we compared the performance of the most serious competitors. In the remaining part of the paper, we describe how we implemented and tested the convex-hull algorithms that rose above the others: plane-sweep, torch, quickhull, and throw-away. We also discuss why the other alternatives mentioned above are not competitive. In particular, we go a bit deeper into some implementation details revealed by a careful code analysis. Finally, we present the results of our workhorse experiments and a totally new set of conclusions.  
The contributions of this work can be summarized as follows.  
* We describe a simple way of making the implementations of convex-hull algorithms robust.
* We identify an error in the original version of torch and propose a corrected, in-place version.
* We prove that, when the coordinates of the \(n\) input points are integers drawn from a bounded universe of size \(U\), quickhull runs in \(O(n\lg U)\) worst-case time. We also explain how its worst-case performance can be reduced to \(O(n\lg n)\)--we call this variant introhull.
* We implement six convex-hull algorithms--plane-sweep, torch, quickhull, poles-first, throw-away, and introhull--and show that these implementations are space-efficient and time-efficient, both in theory and practice.
* We introduce a test framework that can be used to make the programs computing convex hulls self-testing.
* We compare the performance of four space-efficient convex-hull algorithms--plane-sweep, torch, quickhull, and throw-away--in the integer-arithmetic setting.