# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Plane Sweep  
A sequence of points is _monotone_ if the points are sorted according to their \(x\)-coordinates--in non-decreasing or non-increasing order. Let \(p\), \(q\), and \(r\) be three consecutive vertices on a monotone polygonal chain. Recall that a vertex \(q\) of such a chain is _concave_ if there is a left turn or no turn (in the code the condition is not right_turn(p, q, r)) when moving from \(p\) to \(r\) via \(q\). That is, the angle \(\angle pqr\) on the right-hand side with respect to the traversal order is greater than or equal to \(\pi\). The plane-sweep algorithm, proposed by [PERSON] [3], computes the convex hull for a sequence of points as follows:  
(A) Sort the input points in non-decreasing order according to their \(x\)-coordinates. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{3}{c}{(a)} \\ \hline \(n\) & \(x\)**-Sorting** & **Lexicographic Sorting** & **Angular Sorting** \\ \hline \(2^{10}\) & 36.65 & 38.06 & 162.5 \\ \(2^{15}\) & 54.03 & 56.31 & 244.7 \\ \(2^{20}\) & 71.48 & 75.16 & 329.9 \\ \(2^{25}\) & 89.37 & 94.89 & 412.7 \\ \(2^{30}\) & 162.7 & 178.2 & 572.6 \\ \hline \hline \end{tabular}
\begin{tabular}{c c c c} \hline \hline \(n\) & \(x\)**-Sorting** & **Lexicographic Sorting** & **Angular Sorting** \\ \hline \(2^{10}\) & 40.49 & 43.40 & 595.1 \\ \(2^{15}\) & 62.62 & 67.17 & 922.5 \\ \(2^{20}\) & 85.18 & 90.70 & 1247 \\ \(2^{25}\) & 109.1 & 115.5 & 1579 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Performance of introsort for different comparators [nanoseconds per point] for the square data set: (a) Linux computer, (b) Windows computer. * Determine the leftmost point (_west pole_) and the rightmost point (_east pole_). If there are several pole candidates with the same \(x\)-coordinate, let the bottommost of them be the west pole; and on the other end, let the topmost one be the east pole. * Partition the sorted sequence into two parts, the first containing those points that are above or on the line segment determined by the west pole and the east pole, and the second containing the points below that line segment. * Scan the two monotone chains separately by eliminating all concave points that are not on the convex hull. For an early description of this backtracking procedure relying on cross-product computations, see [33]. * Concatenate the computed convex chains to form the final answer. It is worth mentioning that the backtracking procedure used in Step (D) does not work for all polygons as claimed in [33] (for a bug report, see [9]). What is important for our purposes is that it works for monotone polygonal chains provided that the poles are handled as discussed by [PERSON] [3]: All other points that have the same \(x\)-coordinate as the west pole (east pole) are eliminated, except the topmost (bottommost) one provided that it is not a duplicate of the pole. Furthermore, [PERSON] [3] pointed out that in Step (C) it is only necessary to perform the orientation test for points whose \(y\)-coordinate is between the \(y\)-coordinates of the west and east poles. Usually, this will reduce the number of orientation tests performed by a significant fraction. There is a catch hidden in the original description of the algorithm [3]. In Step (C), the partitioning procedure must retain the sorted order of the points, i.e., it must be _stable_. In [PERSON]'s description, it is not specified how this step is to be implemented. It is possible to do stable partitioning in place in linear time (see [34]), but all linear-time algorithms developed for this purpose are considered to be galactic. That means they are known to have a wonderful asymptotic behaviour, but they are never used to actually compute anything [35]. Therefore, it is understandable that [PERSON] implementation of torch[4] used extra arrays of indices to carry out multi-way grouping stably. It is known that the plane-sweep algorithm can be implemented in place.