# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Torch
(3) As the final step, the standard backtracking procedure is applied for the points in the staircase to get the part of the convex hull that is inside \(Q_{1}\). One should observe that the classification, whether a point is a boundary point or not, depends on the original order of the points. For example, consider a multiset of three points \((1,1)\), \((1,2)\), \((1,1)\) given in this order. All these points are dominant in the north-west direction, but the scan only selects the first two as the boundary points. If the order of the last two points had been the opposite, then all three would be classified as boundary points. Since it is unspecified, how a sorting algorithm will order points whose \(x\)-coordinates are equal, in our worst-case constructions we assume that such points are ordered so that all maximal points will be classified as boundary points. The processing in the other quadrants is symmetric. In \(Q_{2}\) the points are scanned from the east pole to the north pole and the staircase goes upwards as in \(Q_{1}\). In \(Q_{3}\) the processing is from the east pole to the south pole and we keep track of the current minimum with respect to the \(y\)-coordinates--so the staircase goes downwards. Finally, in \(Q_{4}\) the points are scanned from the west pole to the south pole and the staircase goes downwards as in \(Q_{3}\). Figure 3: TORCH algorithm illustrated; the staircase in \(Q_{1}\) is displayed in red and all hollow points are discarded during the staircase formation. In Step (C'), to do the grouping, it is only necessary to compare the coordinates, the orientation test is not needed. Also, in Step (D'), only coordinate comparisons are done, no arithmetic operations. In the original description [2], the staircases were concatenated to form an approximation of the convex hull before the final elimination scan. However, doing so may cause the algorithm to malfunction--we will get back to the correctness of this approach in Section 5.3. The asymptotic running time of this algorithm is determined by the sorting steps, which require a total of \(\Theta(n\lg n)\) time in the worst case and in the average case for the best comparison-based sorting method. If the number of maximal points is small as the theory suggests [14], the cost incurred by the evaluation of the orientation tests will be insignificant. Compared to other alternatives, this algorithm is important for two reasons:  
1. Only the \(x\)-coordinates are compared when sorting the points. 2. The number of the orientation tests performed is proportional to the number of maximal points, the coefficient being at most two times the average number of directions the points are dominant in. As to the use of memory, in the implementation of torch[4], [PERSON] used
* four arrays of indices--implemented as std::vector--to keep track of the points in each of the four candidate collections,
* an array of points--implemented as std::vector--to store the boundary points in the approximation, and
* a stack--implemented as std::deque--to store the output. **Fact 1**. : _In the worst-case scenario, [PERSON] implementation may require space for about 8n indices and 8n points for multiset data (or about \(4n\) indices and \(4n\) points for set data) for temporary arrays, or \(h+512\) points and \(\frac{1}{256}h\) pointers for the output stack._  
Proof. : To verify this deficiency for multisets, consider a special input having four poles \((-1,0)\), \((0,1)\), \((1,0)\), \((0,-1)\) and \(n-4\) points at the origin. Since the duplicates are on the border, they should be placed in each of the four candidate collections. Hence, each of the index arrays will be of size \(n-4\). Since the origin is not dominated by any of the poles, none of the duplicates will be eliminated. Therefore, all the duplicates should be included in the approximation of the convex hull, which may contain about \(4n\) points. For sets, in a bad input all input points lie on a line. In this case, all points should be placed in the candidate collections for two of the four quadrants.