# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 5 Testing
### Test Framework  
To be able to verify the correctness of the output automatically, three functions were implemented: same_multiset, convex_polygon, and all_inside. The first function same_multiset takes two multisets of \(n\) and \(m\) points (both specified by a pair of iterators) as its arguments and checks whether these multisets are the same. If \(n\
eq m\), this task is trivial. Otherwise, we copied the given multisets, sorted the copies lexicographically, and verified that the sorted sequences were equal. The second function convex_polygon takes a multiset of \(h\) points (specified by a pair of iterators) as its argument and checks whether the given points form the consecutive vertices of a convex polygon. The third function all_inside takes a multiset of \(n\) points and a convex polygon of \(h\) vertices (both specified by a pair of iterators) as its arguments and checks whether all the points in the multiset are inside or on the boundary of the convex polygon.  
The function same_multiset is easily seen to require \(O(n\lg n)\) time in the worst case. To implement the function convex_polygon in \(O(h)\) worst-case time, we took inspiration from ((26), Exercise 33.1-5).  
\begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline \multirow{2}{*}{\(n\)} & \multicolumn{2}{c}{**3-introhull**} & \multicolumn{2}{c}{**4-introhull**} & \multicolumn{2}{c}{poles-first**} & \multicolumn{2}{c}{throw-away} \\  & **Square** & **Disc** & **Square** & **Disc** & **Square** & **Disc** & **Square** & **Disc** \\ \hline \(2^{10}\) & 3.37 & 12.0 & 0.06 & 0.30 & 51.0 & 37.9 & 4.29 & 12.2 \\ \(2^{15}\) & 0.60 & 10.2 & 0.02 & 0.85 & 50.9 & 36.5 & 0.71 & 10.2 \\ \(2^{20}\) & 0.10 & 9.99 & 0.00 & 0.66 & 51.3 & 36.3 & 0.12 & 9.99 \\ \(2^{25}\) & 0.01 & 9.97 & 0.00 & 0.64 & 50.6 & 36.3 & 0.01 & 9.97 \\ \(2^{30}\) & 0.00 & 9.97 & 0.00 & 0.64 & 50.4 & 36.3 & 0.00 & 9.97 \\ \hline \hline \end{tabular}
\end{table}
Table 3: The average number of points left after the elimination [%] for different strategies for the two data sets.  
The function all_inside runs in \(O(n\lg h)\) worst-case time since it performs two binary searches over the convex polygon of size \(h\) for each of the \(n\) points.  
The test suite has--among others--the following test cases, each implemented as a separate function. The names of the test cases were selected to indicate what is being tested:  
* empty_set,
* one_point,
* two_points,
* three_points_on_a_vertical_line,
* three_points_on_a_horizontal_line,
* ten_equal_points,
* four_poles_with_duplicates,
* random_points_on_a_parabola,
* random_points_in_a_square (10,000 test cases),
* corners_of_the_universe.  
As one can see from this list, we expect that the programs are able to handle multiset data, degenerate cases, and arithmetic overflows.  
To use the test suite, every algorithm must be implemented in its own namespace which provides a function solve to be used to compute convex hulls and a function check to be used to check the validity of the answer. Normally, a checker takes a copy of the input, solves the problem with a solver, and uses the tools in our test suite to check that the points in the output are the same as those in the input, that the computed hull is a convex polygon, and that all the input points are inside or on the boundary of the computed convex hull. That is, the programs can be made self-testing if wanted--but the time and space overhead for doing this is quite high due to sorting and extra copies taken.