# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Quickhull  
The quickhull algorithm, which mimics quicksort, has been reinvented several times (see, e.g., [8; 9; 10]). The key subroutine is again the one that chains two extreme points together, but now it is implemented recursively (for a visualization, see Figure 4). The parameters are an oriented line segment \(\overrightarrow{p\mskip-1.0 mu \mskip-1. [PERSON] used the QHULL program [41] in his experiments. However, he did not give any details how he used this library routine so, unfortunately, we have not been able to repeat his experiments. From the QHULL manual [42], one can read that the program is designed to  
* solve many geometric problems,
* work in the \(d\)-dimensional space for any \(d\geq 2\),
* be output sensitive,
* reduce space requirements, and
* handle most of the rounding errors caused by floating-point arithmetic. Based on this description, we got a feeling that this is like using a sledgehammer to crack a nut. Simply, specialized code designed for finding the two-dimensional convex hull--and only that--should be faster. After doing the implementation work, the resulting code was less than 200 lines long. As an extra bonus,  
* we had full control over any further tuning and
* we could be sure that the computed output was correct as, also here, we relied on exact integer arithmetic. In our implementation of QUICKhull we followed the guidelines given by [PERSON] [8] (the space-efficient alternative): (1) As in plane-sweep, find the two poles, the west pole \(p\) and the east pole \(r\). Put \(p\) first and \(r\) last in the sequence. (2) Partition the remaining points between \(p\) and \(r\) into upper-hull and lower-hull candidates: \(C_{1}\) contains those points that lie above or on the line segment \(\overline{p}\overline{r}\) and \(C_{2}\) those that lie below it. (3) Call the recursive elimination routine described above for the upper-hull candidates with the parameters \(\overline{p}\overline{r}\) and \(C_{1}\). (4) Move \(r\) just after the upper chain computed and the eliminated points after the lower-hull candidates. (5) Apply the recursive elimination routine for the lower-hull candidates with the parameters \(\overline{r}\overline{p}\) and \(C_{2}\). (6) Now the point sequence is rearranged such that (a) \(p\) comes first, (b) the computed upper chain follows it, (c) \(r\) comes next, (d) then comes the computed lower chain, and (e) all the eliminated points are at the end. Lastly, return the position of the first eliminated point (or the past-the-end position if no such point exists) as the final answer. As a matter of fact, the analogy with QUICKORT[16] is not entirely correct since it is a randomized algorithm--a random element is used as the pivot. [PERSON], [PERSON] et al. [41] addressed both randomized  
Figure 4: A visualization of the general recursive step in QUICKhull. and the non-randomized versions of Quickhull. [PERSON] [8] made the analogy with Quickersort[43], in which the middle element is used as the pivot and the stack size is kept logarithmic. In our opinion, this analogy is not quite correct either. It would be more appropriate to see the algorithm as an incarnation of the Middle-of-the-range Quicksort where for each subproblem the minimum and maximum values are determined and their mean is used as the pivot. If the elements being sorted are integers drawn from a universe of size \(U\), the worst-case running time of this variant is \(O(n\lg U)\). [PERSON] [8] showed that the worst case of Quickhull is \(O(nh)\). However, [PERSON] and [PERSON] [44] proved that in the average case the algorithm runs in \(O(n)\) expected time. The result holds when the points are chosen uniformly and independently at random from a bounded convex region. Actually, their proof is stronger, because by exploiting the connection to Middle-of-the-range Quicksort, it can be applied to get the following:  
**Fact 2**. : _When the coordinates of the points are integers drawn from a bounded universe of size \(U\), the worst-case running time of Quickhull is \(O(n\lg U)\)._  
Proof.