# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 6 Workhorse Experiments
### Experimental Design  
To make the programs robust, we considered three alternative approaches when implementing the geometric primitives:  
**Multi-precision arithmetic.**: As described in Section 2.3, we performed intermediate calculations using the multi-precision integers available at the CPH STL [22]. This solution is generic, works for any type of integer coordinates, and the program code is beautiful.
**Double-precision arithmetic.**: We specialized the geometric primitives to use double-precision integers (signed/unsigned long long), kept track of all the possible overflows, and dealt with them accordingly. This ad-hoc solution relies on the fact that the coordinates are of type int. Unfortunately, we must admit that the resulting code is inelegant.
**Floating-point filter.**: We converted the coordinates to floating-point numbers and performed the intermediate calculations using them. Only if the result was not known to be correct due to accumulation of rounding errors would we use the multi-precision numbers to redo the  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **Worst Case** & **Average Case** & **Work Space** \\ \hline introsort[27] & \(\Theta(n\lg n)\) & \(\Theta(n\lg n)\) & \(W(n)\equiv\mathrm{O}(\lg n)\) \\ plane-sweep[3] & \(\Theta(n\lg n)\) & \(\Theta(n\lg n)\) & \(\mathcal{O}(1)+W(n)\) [15]*  \\ torch[2] & \(\Theta(n\lg n)\) & \(\Theta(n\lg n)\) & \(\mathcal{O}(1)+W(n)\) [15] \\ quickhull[8; 9; 10] & \(\mathcal{O}(n\lg U)\) [*] & \(\Theta(n)\) [44] & \(\mathrm{O}(\lg U)\) [*] \\ throw-away[12] & \(\Theta(n\lg n)\) & \(\Theta(n)\) & \(\mathcal{O}(1)+W(n)\) [*] \\ \hline \hline \end{tabular}
\end{table}
Table 4: A summary of the theoretical performance of the algorithms considered. The average-case running time is for the square data set. Here \(n\) denotes the size of the input, \(U\) the size of the coordinate universe, and \(W(n)\) the amount of the work space required by the sorting routine in use. [*] means that the result was presented in this paper.  
calculations. In the present case, we employed [PERSON]'s filter coded in [45]. A readable explanation of how the filter works can be found in [46].  
Most of our programs can be run in any of the three modes just by specifying which arithmetic to use in the realization of the geometric primitives.  
In our experiments, we fixed the coordinates of the points to be integers of type int, each occupying 32 bits. Hence, the multi-precision solution had to use integers that were wider than any of the built-in integers. The double-precision solution could operate on built-in integers of 64 bits. In our micro-benchmarks, the ad-hoc solution that solely relied on built-in types was the fastest of these three approaches. When the coordinates were of type int, we did not want to slow down the programs unnecessarily, so we used the ad-hoc solution in the experiments reported here. Since we are not reliant on any multi-precision integer library, it should be easier for others to replicate the experiments and reproduce the results.  
In earlier studies, the number of orientation tests and that of coordinate comparisons have been targets for optimization. Since the algorithms reorder the points in place, the number of coordinate moves is also a relevant performance indicator. Hence, in addition to the amount of CPU time, we measured the number of orientation tests, coordinate comparisons, and coordinate moves. The number of orientation tests performed is proportional to \(n\) in the worst case for plane-sweep, torch, and throw-away; and in the average case for quickhull. The number of coordinate comparisons and coordinate moves is proportional to \(n\lg n\) in the worst and average cases for plane-sweep and torch, and to \(n\) in the average case for quickhull and throw-away.