# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Torch  
The following definitions are from [37]: (1) A _rectilinear line segment_ is a line segment oriented parallel to either the \(x\)-axis or the \(y\)-axis. (2) A point set is _rectilinear convex_ if for any two of its points which determine a rectilinear line segment, the line segment lies entirely in the given set. (3) Given a multiset \(S\) of points, its (_connected_) _rectilinear convex hull_ is the smallest connected rectilinear convex set enclosing all the points of \(S\). Roughly speaking, a rectilinear convex hull connects all the maximal points with four rectilinear curves. At the abstract level, torch[2] operates in two stages: (1) Find the points on the rectilinear convex hull. (2) Refine this approximation by discarding all concave points from it. The correctness of this approach follows directly from the fact that the rectilinear convexity is a looser condition than the normal convexity. [PERSON] et al. [37] showed how to compute the rectilinear convex hull in \(O(n\lg n)\) time and \(O(n)\) space. If plane-sweep is used to do the refinement, the overall running time of this procedure is \(O(n\lg n)\). A similar approach was proposed by [PERSON] et al. [14] (see also [38; 39])--they computed all maximal points; they were not interested in the rectilinear curvature. They proved that, under the assumption that the points are chosen from a probability distribution in which each coordinate of a point is chosen independently of all other coordinates, the number of maximal points is \(O(\lg n)\). Using this fact, one can develop algorithms for computing maxima and convex hulls (for a historical review, see [39]), for which the expected running time is \(O(n)\) and the worst-case running time \(O(n\lg n)\). [PERSON] [2] combined the rectilinear-convex-hull algorithm by [PERSON] et al. [37] and the plane-sweep algorithm [3] as follows: (1) By integrating the two algorithms better, redundant sorting computations can be avoided. (2) By replacing lexicographic sorting with \(x\)-sorting, a superset can be computed faster even though now it may include some extra maximal points that lie on the periphery of the rectilinear convex hull--i.e., the computation of the rectilinear convex hull is not fully accurate, but for our purpose these extra maximal points are by no means harmful. We call the points selected by [PERSON] heuristic algorithm _boundary points_. In torch, Steps (C) and (D) of the plane-sweep algorithm are replaced with the following three steps (for an illustration, see Figure 3):* Find the topmost point (_north pole_) and the bottommost point (_south pole_) by one additional scan and resolve the ties in a similar fashion as in Step (B). * Group the input points into four (overlapping) candidate collections such that, for \(i\in\{1,2,3,4\}\), the \(i\)'th collection contains the points that are not dominated by the adjacent poles in the respective direction (north-west, north-east, south-east, or south-west), i.e., these points are in the quadrant \(Q_{i}\) of Figure 3. Note that the quadrant includes the borders. * In each of the candidate collections, compute the boundary points before discarding the concave points that are not in the output polygon. Let us look at Step (D') a little more thoroughly by considering what is done in \(Q_{1}\): (1) The points in \(Q_{1}\) are sorted according to their \(x\)-coordinates. (2) The sorted sequence is scanned from the west pole to the north pole and a point is selected as a boundary point if its \(y\)-coordinate is larger than or equal to the maximum \(y\)-coordinate seen so far. That is, the selected points form a monotonic sequence both with respect to their \(x\)-coordinates and \(y\)-coordinates; we call such a sequence a _staircase_. Since the points on the computed staircase are all maximal and only maximal points on a rectilinear line segment determined by two other points may be discarded, the staircase must contain all vertices of the convex hull that are in \(Q_{1}\).