# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 2 Preliminaries
### Test Environment  
The experiments to be discussed were run on two computers: one running Linux and the other running Windows. Both computers could be characterized as standard laptops that one can buy from any well-stocked computer store. A summary of the test environments is given in Table 1. Although both computers had four cores, the experiments were run on a single core.  
\begin{table}
\begin{tabular}{l}
**Processor.** Intel® CoreTM i7-6600U CPU @ 2.6 GHz (turbo-boost up to 3.6 GHz)—4 cores \\
**Word size.** 64 bits \\
**First-level data cache.** 8-way set-associative, 64 sets, 4 \(\times\) 32 KB \\
**First-level instruction cache.** 8-way set-associative, 64 sets, 4 \(\times\) 32 KB \\
**Second-level cache.** 4-way set-associative, 1 024 sets, 256 KB \\
**Third-level cache.** 16-way set-associative, 4 096 sets, 4.096 MB \\
**Main memory.** 8.038 GB \\
**Operating system.** Ubuntu 17.10 \\
**Kernel.** Linux 4.13.0-16-generic \\
**Compiler.** g++ 7.2.0 \\
**Compiler options.** -03 -std=c++17 -x c++ -Wall –Wextra –fconcepts \\ \end{tabular}
\end{table}
Table 1: Hardware and software in use: (a) Linux computer, (b) Windows computer.  
As the input for the programs, we used three types of data:  
**Square data set.**: The coordinates of the points were random integers uniformly distributed over the interval \([-2^{31}\cdot 2^{31}]\) (i.e., random ints). The expected size of the output is \(O(\lg n)\)[14].
**Disc data set.**: As above, the coordinates of the points were random ints, but only the points inside the circle centred at the origin \((0,0)\) with the radius \(2^{31}-1\) were accepted to the input collection. In this case, the expected size of the output is \(O(n^{1/3})\).
**Bell data set.**: The points were drawn according to a two-dimensional normal distribution by rounding each coordinate to the nearest integer value (of type int). The mean value of the distribution was 0 and the standard deviation \(r/(2+\log_{e}(n))\) where \(r=2^{31}-1\). For this data set, the expected size of the output is \(O(\sqrt{\lg n}\,)\).  
All our programs used the same point class template that took the type of the coordinates as its template parameter. The implementation of this class was straightforward: It had two public data members \(x\) and \(y\), it had a default constructor and a parameterized constructor, and it supported the operations \(\{\)\(\)\(\equiv\), \(\)\(\
eq\), \(\)\(<\), \(>\)\(\}\) for any pair of points.  
None of the considered algorithms use random-access capabilities to a large extent. Therefore, we did not expect to see any significant cache effects in our experiments. Based on the memory configuration of the test computers, we wanted to check what happened when the problem instances became bigger than the capacity of different memory levels. In particular, it seemed not to be necessary to plot detailed curves of the running times.  
The points were stored in an array. We report the test results for five values of \(n\): \(2^{10}\), \(2^{15}\), \(2^{20}\), \(2^{25}\), and \(2^{30}\). Observe that for the largest test case, there could be at most one array of \(2^{30}\) points in the internal memory of the Linux computer, while the Windows computer could not handle that.  
Be aware that the reported measurement results are scaled: For every performance indicator, if \(X\) is the observed number, we report \(X/n\). That is, a constant means linear performance. To avoid problems with inadequate clock precision and pseudo-random number generation, a test for \(n=2^{i}\) was repeated \(\lceil 2^{27}/2^{i}\rceil\) times; each repetition was done with a new input array. The input arrays were pre-generated and statistically independent.