# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 7 Conclusions
discussed in this paper are publicly available; a frozen release is available as a supplement from the journal ([[http://www.mdpi.com/1999-4893/11/12/195/s1](http://www.mdpi.com/1999-4893/11/12/195/s1)]([http://www.mdpi.com/1999-4893/11/12/195/s1](http://www.mdpi.com/1999-4893/11/12/195/s1))) and the latest updated release from the home page of the CPH STL [49]. The focus in this paper was on correctness and quality--both in the implementations and experiments. If raw speed is what you need, you may follow some of the following avenues:  
**Smarter sorting. **: In a sorting-based approach, when sorting a sequence of points according to their \(x\)-coordinates, if two points are seen to have the same \(x\)-coordinate, the point with the smaller (or larger) \(y\)-coordinate could be eliminated. More generally, it is possible to sort \(n\) elements having at most \(\ell\) different values in \(O(n\lg\ell)\) worst-case time. Another possibility is to use bucketsort when sorting the points [28]. **Further tuning. **: In this study, Quickhull was one of the winners. However, a careful analysis shows that Quickhull does redundant orientation tests (as pointed out in [28; 50]). By removing some of the redundant work, Quickhull can be made even quicker. **More aggressive elimination. **: The idea of eliminating interior points during the computation is good! However, in contemporary computers, sorting is fast. So an elimination procedure should not be complicated. In a follow-up paper [51], we implemented a bucketing algorithm ([52], Section 4.4), for which the elimination overhead is three scans and the elimination effectiveness is better than that for the throw-away algorithm. The work space used by this algorithm is \(O(\sqrt{n})\) words, but because of random access its competitive advantage may fade away when the problem size becomes large. **Better integration. **: Many good algorithms are hybrids of several other algorithms. One of the goals is to reach good worst-case and average-case performance at the same time. Taking inspiration from introsort [27], we proposed introhull that combines Quickhull [8] and plane-sweep[3]. [PERSON] torch[2] combines the rectilinear-convex-hull algorithm by [PERSON] et al. [37] and plane-sweep. However, because of introsort, the average-case running of this hybrid is \(\Theta(n\lg n)\). As shown by [PERSON] et al. [14], a divide-and-conquer algorithm could be used to compute a superset which will reduce the average case of the combined algorithm to \(O(n)\), keeping the worst case unchanged. Does this pruning-before-sorting approach have any practical significance? **Parallel processing. **: In our benchmarks, only one core was in use even though both of our test computers had four cores. Some previous studies (see, e.g., [53]) have shown that the additional cores can be used to speed up Quicksort, Quickhull, and other divide-and-conquer algorithms. A further study, where speed is at the focus, must consider how technological changes affect the existing algorithms. **Supplementary Materials:**: The programs used in the experiments, implemented and benchmarked are available--in their latest updated versions--via the home page of the CPH STL ([[http://www.cphstl.dk](http://www.cphstl.dk)]([http://www.cphstl.dk](http://www.cphstl.dk))) in the form of a pdf file and a tar archive [49]. As a supplement to this text, a single zip file is available online at [[http://www.mdpi.com/1999-4893/11/12/195/s1](http://www.mdpi.com/1999-4893/11/12/195/s1)]([http://www.mdpi.com/1999-4893/11/12/195/s1](http://www.mdpi.com/1999-4893/11/12/195/s1)) that contains the source code of the programs, and a document \"Supplement: Relevant source code\" explaining how to use the programs and how to redo the experiments. **Author Contributions:**: Methodology, A.N.G. and J.K.; Software, A.N.G. and J.K.; Supervision, J.K.; Validation, A.N.G. ; Writing--precursor, A.N.G. ; Writing--review and editing, J.K.
**Funding:**: This research received no external funding.