# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 6 Workhorse Experiments
### Time Performance  
In our first set of experiments, we measured the amount of CPU time used by the competitors to compute the convex hull for the considered data sets. The results are shown in Table 5 (square), Table 6 (disc), and Table 7 (bell). The results are unambiguous: For randomly generated data, both quickhull and throw-away are quick! Both of these methods can avoid the sorting bottleneck, which torch does not try to do. We could force quickhull to perform worse than the others when the points were drawn from an arc of a parabola. However, we could only make it a constant factor slower; we could not provoke the \(\Theta(nh)\) behaviour because of the restricted precision of the coordinates. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & & \multicolumn{3}{c}{(**a**)} \\ \hline \(n\) & introsort & plane-sweep & torch & quickhull & throw-away \\ \hline \(2^{10}\) & 36.65 & 55.92 & 49.62 & 34.67 & 27.32 \\ \(2^{15}\) & 54.03 & 72.18 & 64.68 & 30.92 & 26.02 \\ \(2^{20}\) & 71.48 & 89.24 & 82.40 & 31.06 & 24.40 \\ \(2^{25}\) & 89.37 & 107.9 & 101.1 & 30.78 & 25.03 \\ \(2^{30}\) & 162.7 & 281.3 & 334.4 & 245.8 & 247.4 \\ \hline \multicolumn{5}{c}{(**b**)} \\ \hline \(n\) & introsort & plane-sweep & torch & quickhull & throw-away \\ \hline \(2^{10}\) & 40.52 & 53.27 & 62.40 & 51.98 & 34.50 \\ \(2^{15}\) & 64.37 & 73.86 & 84.40 & 48.67 & 30.90 \\ \(2^{20}\) & 83.76 & 94.82 & 106.5 & 49.54 & 30.52 \\ \(2^{25}\) & 106.8 & 124.6 & 130.4 & 48.92 & 30.58 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: The running time of the competitors [in nanoseconds per point] for the square data set: (**a**) Linux computer, (**b**) Windows computer. When looking at the results, it is eye-catching that, in the Linux computer, the numbers are exceptionally high for the largest problem instance. We observed that, when the size of the input was close to the maximum capacity of main memory, the memory operations became more expensive. The changes in the running times looked normal up to \(n=2^{29}\), but after this saturation point the slowdown was noticeable. In most cases the execution time per point increases as the input instances get larger, while in some cases the cost may stagnate or even get smaller. A logarithmic increase indicates a dominating \(O(n\lg n)\) cost, as the execution times are divided by \(n\). Sorting naturally follows this growth. As both torch and plane-sweep sort a fraction of points a few times, the cost of both is in direct relation to the sorting cost. Both quickhull and throw-away are not directly bounded by this, since they perform some elimination before reverting to sorting. Especially, we note that quickhull tends to become slightly faster (per point) on larger instances. There is a trade-off between the amount of work used for elimination and that used for sorting the remaining points. For randomly generated data, \(h\) tends to grow much slower than \(n\), so for quickhull and throw-away the cost incurred by sorting will gradually vanish. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{4}{c}{(**a**)} \\ \hline \(\#\) & **introsort** & **plane-sweep** & **torch** & **quickhull** & **throw-away** \\ \hline \(2^{10}\) & 36.31 & 52.75 & 55.01 & 33.04 & 27.31 \\ \(2^{15}\) & 53.84 & 69.10 & 69.94 & 30.90 & 26.96 \\ \(2^{20}\) & 71.20 & 86.21 & 87.37 & 31.06 & 28.33 \\ \(2^{25}\) & 88.94 & 104.1 & 105.4 & 31.59 & 30.96 \\ \(2^{30}\) & 212.5 & 281.3 & 350.9 & 226.3 & 242.3 \\ \hline \hline \end{tabular}
\begin{tabular}{c c c c c c} \hline \hline \(n\) & **introsort** & **plane-sweep** & **torch** & **quickhull** & **throw-away** \\ \hline \(2^{10}\) & 40.16 & 58.66 & 58.62 & 47.48 & 32.84 \\ \(2^{15}\) & 62.19 & 78.96 & 79.67 & 44.64 & 32.41 \\ \(2^{20}\) & 85.24 & 101.9 & 102.2 & 45.31 & 34.13 \\ \(2^{25}\) & 108.6 & 126.6 & 125.7 & 46.46 & 36.29 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: The running time of the competitors [in nanoseconds per point] for the disc data set: (**a**) Linux computer, (**b**) Windows computer. \begin{table}