# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Other Elimination Heuristics
From this it follows that the expected number of points left after elimination must be larger than \((1-\frac{2\sqrt{2}}{\pi})n\), as claimed. An implementation of the throw-away algorithm was described in ([PERSON] and [PERSON], 2015). The authors tried to make the integration between the preprocessing step and the plane-sweep algorithm smooth to prevent repetitive work in the latter (recomputation of the poles and orientation tests in partitioning). However, the linear space needed for this integration was a high price to pay because, after elimination, the main bulk of the work is done in sorting. Yet another alternative is to see quickhull as an elimination algorithm. To integrate quickhull with plane-sweep, we reimplemented it in an introspective way. When the recursion depth reached some predetermined threshold, we stopped the recursion and solved the subproblem at hand using plane-sweep. For integer \(k\), let \(k\)-introhull be the member of the family of quickhull algorithms for which the threshold is \(k\). For example, 3-introhull is quite similar to throw-away elimination. The member \((\lg n)\)-introhull is significant, because the amount of work done at the top portion of the recursion tree will be bounded by \(O(n\lg n)\) and the amount of the work done when solving the subproblems at the leaves will also sum up to \(O(n\lg n)\). For this variant, the worst-case running time is \(O(n\lg n)\) as for the plane-sweep algorithm. Still, the average-case running time is \(O(n)\) since the expected number of points left decreases geometrically with recursion depth. From this it follows that the expected number of points left at recursion level \(\lg n\) is \(O(1)\). Figure 5: The region uncovered by throw-away preprocessing for the disc data set. By the observation of [PERSON] and [PERSON] (2018), for \(k\)-introhull, the expected number of points left after the elimination should at most be around \(\frac{1}{2^{k}}n\) for both of our data sets. To verify this bound in practice, we measured the expected number of points left after elimination for the two data sets. To understand how \(k\)-introhull works compared to the other elimination heuristics, we made the same experiments for them, too. The numbers in Table 3 are the averages of many repetitions, except those on the last row. The elimination effectiveness of poles-first is not impressive--although there are no surprises in the numbers. The throw-away algorithm works better; it is designed for the square data set, but the limit 9.968 % in the elimination effectiveness for the disc data set leaves some shadows for this algorithm. The numbers for 3-introhull are basically the same as those for throw-away. Roughly speaking, in quickhull all the work is done at a few first recursion levels. Compared to the static throw-away algorithm, the elimination strategy applied in quickhull is adaptive, and it can be made finer by increasing \(k\). If good worst-case efficiency is important and one wants to use quickhull, we can warmly recommend \((\lg n)\)-introhull. The overhead compared to the standard set-up is one if statement in each recursive call to check if the leaf level has been reached. So the worst-case performance of quickhull can be reduced from \(O(n\lg U)\) to \(O(n\lg n)\) if wanted.