# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 3 Pilot Experiments
### Rotational Sweep  
The rotational-sweep algorithm due to [PERSON] [5] is historically important; it was the first algorithm that could compute the convex hull of \(n\) points in \(O(n\lg n)\) worst-case time. This algorithm works as follows: (1) Find a point \(o\) that is on the convex hull (e.g., a point that is lexicographically the smallest). (2) Sort all the points around \(o\) lexicographically by polar angle and distance from \(o\). (3) Scan the formed star-shaped polygon in clockwise order by repeatedly considering triples \((p,q,r)\) of consecutive points on this dynamically-changing polygon and eliminate \(q\) if there is not a right turn at \(q\) when moving from \(p\) to \(r\) via \(q\).  
Figure 1: The left-turn predicate written in C++. The compile-time function cphmpl::width<T>> returns the width of the coordinates of type T in bits. The class template cphst1::Z<b>> provides fixed-width integers; the width of the numbers is \(\mathtt{b}\) bits and, for numbers of this type, the same operations are supported as for built-in integers.  
[PERSON] [2] did not release his implementation of rotational-sweep, but he referred to the implementation described in [25] which closely follows the description given in the textbook by [PERSON] et al. ([26], Section 33.3). This code had some issues that we would handle differently:  
* The routine did not operate in place, but the output was produced on a separate stack.
* The routine had the same robustness issues as [PERSON] program: The arithmetic operations in the orientation test and the distance calculation could overflow.
* The C library QSORT was used in sorting; this program is known to be slower and less reliable than the C++ standard-library introsort[27]. [PERSON] used introsort in his own program.  
[PERSON] [3] emphasized that, compared to his own algorithm, rotational-sweep calls the orientation predicate \(\Theta(n\lg n)\) times. To understand the effect of angular sorting, we performed a benchmark where we sorted a sequence of \(n\) points using introsort[27]. We considered three types of comparators; these were given as lambda functions for std::sort. Here P is the type of the points and o the point around which the angular sorting is done; both are specified in the surrounding code.  
\(x\)-sorting.  
[](P const& p, P const& q) \(\rightarrow\) bool {  return p.x \(<\) q.x;  }  
Lexicographic sorting.  
[](P const& p, P const& q) \(\rightarrow\) bool {  return (p.x \(<\) q.x) or (p.x == q.x and p.y \(<\) q.y);  }  
Angular sorting.  
[&](P const& p, P const& q) \(\rightarrow\) bool {  int turn = orientation(o, p, q);  if (turn == 0) {  return (L\({}_{\infty}\)distance(o, p) \(<\) L\({}_{\infty}\)distance(o, q));  }  return (turn == +1);  }  
In the above, the functions orientation and L\({}_{\infty}\)distance--which do what their names indicate--were implemented using multi-precision integers in the same way as the function left_turn in Figure 1.  
The results of this micro-benchmark are shown in Table 2. Based on these results, we can safely ignore any convex-hull algorithm that requires full angular sorting.