# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Torch
Again, none of the points on the line are dominated by the poles. Therefore, the approximation may contain \(2n\) points. For C++ standard-library vectors, the total amount of space allocated can be two times larger than what is actually needed (see, for example, the benchmarks reported in [40]). In the C++ standard library, by default a stack is implemented as a deque which is realized by maintaining a vector of pointers to memory segments (of, say, 512 points). From this discussion, the stated bounds follow. It should be emphasized that this heuristic algorithm only reduces the number of orientation tests performed in the average case. There is no asymptotic improvement in the overall running time--in the worst case or in the average case--because the pruning is done after the sorting. The plane-sweep algorithm may perform the orientation test up to about \(3n\) times. For the special input described above, TORCH may perform the orientation test at least \(4n-O(1)\) times, so in the worst case there is no improvement in this respect either. As we utilize an implementation improvement, where not all maximal points are computed, but only those that form a staircase in each of the four quadrants, some of the maximal points may be eliminated already during this staircase formation. Experimentally, the highest number of orientation tests observed to be performed by TORCH was \(3.33n\). Due to the correctness issues and excessive use of memory, we decided to implement our own version of TORCH. Our corrected version requires \(O(1)\) or \(O(\lg n)\) words of additional memory,depending on whether heapsort[36] or introsort[27] is used in sorting. After finding the poles, the algorithm processes the points in four phases:  
1. Partition the input sequence such that the points in the north-west quadrant (\(Q_{1}\) in Figure 3) determined by the west and north poles are moved to the beginning and the remaining points to the end (normal two-way partitioning). 2. Sort the points in \(Q_{1}\) according to their \(x\)-coordinates in non-decreasing order. 3. Find the boundary points in \(Q_{1}\) and move the eliminated points at the end of the zone occupied by the points of \(Q_{1}\). Here the staircase goes upwards. 4. Scan the boundary points in \(Q_{1}\) to determine the convex chain from the west pole to the north pole. Again, the eliminated points are put at the end of the corresponding zone. 5. Consider all the remaining points (also those eliminated earlier) and partition the zone occupied by them into two so that the points in \(Q_{2}\) become just after the west-north chain ending with the north pole. 6. Sort the points in \(Q_{2}\) according to their \(x\)-coordinates in non-increasing order. 7. Find the boundary points in \(Q_{2}\) as in Step (1c). Also here the staircase goes upwards. 8. Reverse the boundary points in place so that their \(x\)-order becomes non-decreasing. 9. Continue the scan that removes the concave points from the boundary points to get the convex chain from the north pole to the east pole. 10. Compute the south-east chain of the convex hull for the points in \(Q_{3}\) as in Step (2), except that now the staircase goes downwards and the reversal of the boundary points is not necessary. 11. Compute the south-west chain of the convex hull for the points in \(Q_{4}\) as in Step (2), except that now the sorting order is non-decreasing and the staircase goes downwards. It is important to observe that any point in the middle of Figure 3 is dominated by one of the poles in each of the four directions. Hence, these points are never moved to a candidate collection. However, if a point lies in two (or more) quadrants, it will take part in several sorting computations. (In Figure 3, move the east pole up and see what happens.) To recover from this, it might be advantageous to use an adaptive sorting algorithm.