# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 7 Conclusions  
We repeat our general conclusion that the quality of implementation really matters in experimental studies. A solid implementation should be based on a correct algorithm. Additional proper testing is necessary before running any experiments. As showcased by this paper, failing to do this may lead to unreliable results and questionable conclusions. The bottom line is that the value of experimental results and their contribution to science are strictly limited by the quality of implementation. We would like to summarize our findings as follows. **Robustness. **: Everyone in computer science knows the problems associated with arithmetic overflows. In the convex-hull algorithms, one has to analyse a single-line formula to determine the maximum precision needed when doing the calculations in an orientation test. This is a type function that maps the type of the input coordinates to the type of some higher-precision numeric type. This mapping can be carried out at compile time. This solution leads to fast performance since the compiler can optimize the generated code. Our message is that a heavyweight static-analysis tool, described in [47], to do automatic code analysis may be an overkill in this particular application, even thought the aim is the same--perform as much work at compile time as possible. On the other end, arbitrary-precision arithmetic provided, for example, by GMP [48] may also be an overkill because the width of the numbers is extended dynamically at run time. **Correctness. **: Experimental results can be misleading if the programs do not produce a correct answer. Naturally, testing is not enough to guarantee correctness, but it is a necessary evil to avoid great humiliation. In the case of convex-hull algorithms, a test framework similar to ours can help improve code quality. **Space requirements. **: By using less memory, one can avoid the overhead caused by memory management and incur less cache misses. There is a big difference if the amount of extra space used is \(\Theta(n)\) or \(O(1)\) words. We explained how plane-sweep, torch, poles-first, and throw-away can be implemented in place. **Arithmetic complexity. **: For in-situ variants in the integer-arithmetic setting, our experiments indicate that the improvement provided by torch compared to plane-sweep is marginal. However, the situation may change if the arithmetic operations are expensive. Namely, it is expected that torch will execute a fewer number of arithmetic operations than the other investigated algorithms, which always perform \(\Omega(n)\) orientation tests. **Reproducibility. **: In experimental work, a \"key principle is that the experiment should be verifiable and reproducible\" ([1], Chapter 14). All the programs and scripts used to run the experiments \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(n\) & **introsort** & **plane-sweep** & **torch** & **quickhull** & **throw-away** \\ \hline \(2^{10}\) & 19.1 & 30.1 & 21.3 & 15.2 & 21.2 \\ \(2^{15}\) & 26.2 & 37.2 & 28.0 & 14.7 & 20.2 \\ \(2^{20}\) & 33.3 & 44.3 & 35.3 & 14.5 & 20.1 \\ \(2^{25}\) & 40.5 & 51.5 & 42.3 & 14.5 & 20.0 \\ \(2^{30}\) & 47.4 & \(57.8\) & 49.2 & 16.4 & 20.4 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: The number of coordinate moves performed by the competitors [divided by \(n\)] for the square data set. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(n\) & **introsort** & **plane-sweep** & **torch** & **quickhull** & **throw-away** \\ \hline \(2^{10}\) & 12.0 & 14.8 & 21.3 & 2.26 & 15.0 \\ \(2^{15}\) & 18.1 & 20.9 & 28.0 & 2.25 & 15.0 \\ \(2^{20}\) & 24.2 & 27.1 & 35.3 & 2.25 & 15.0 \\ \(2^{25}\) & 30.2 & 33.3 & 42.3 & 2.25 & 15.1 \\ \(2^{30}\) & 36.5 & 39.0 & 49.2 & 2.25 & 15.2 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: The number of coordinate comparisons performed by the competitors [divided by \(n\)] for the square data set.