# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Other Elimination Heuristics  
The Quickhull algorithm brings forth the important issue of eliminating interior points--if there are any--before sorting. When computing the convex hull, one has to consider all directions when finding the extreme points. A rough approximation of the convex hull is obtained by considering only a few specific directions. As discussed in several papers (see, for example, [3; 11; 12]), by eliminating the points falling inside or on the boundary of such an approximation, the problem size can often be reduced considerably. After this kind of preprocessing, any of the algorithms mentioned earlier could be used to process the remaining points. For a good elimination strategy two things are important: (1) speed and (2) effectiveness. To achieve high speed, the elimination procedure should be simple. With good elimination effectiveness, the cost of the main algorithm may become insignificant. So there is a trade-off between the two. [PERSON] and [PERSON] [11] found the extrema in four equispaced directions--those determined by the coordinate axes. Also, [PERSON] [3] mentioned this as an option to achieve further saving in the average-case performance of the plane-sweep algorithm. This poles-first algorithm, as we name it, works as follows: (1) Compute the west, north, east, and south poles. (2) Eliminate the points inside or on the perimeter of the quadrilateral (or triangle or line segment) having these poles as its vertices. (3) Apply the plane-sweep algorithm for the remaining points. The elimination overhead is two scans--so the elimination procedure is fast. Unfortunately, it is not always efficient. For example, in the case that the west and south poles coincide, and the north and east poles coincide, only the points on the line segment determined by the two poles will be eliminated. [PERSON] and [PERSON] [12] used eight equispaced directions. We name this algorithm throw-away; we implemented it as follows: (1) Find the extreme points in eight predetermineddirections: \(\pm x\), \(\pm y\), \(\pm(x+y)\), and \(\pm(x-y)\). (2) Eliminate all the points inside or on the boundary of the convex polygon determined by the found points. (3) Apply the plane-sweep algorithm for the remaining points. Also here, the elimination overhead is two scans: one max-finding scan to find the extrema and another partitioning scan to do the elimination. If the plane-sweep algorithm used heapsort, the whole algorithm would work in place; with introsort it works in situ instead. [PERSON] and [PERSON] (2015) proved that for the square data set the number of points left after throw-away preprocessing will be small. Unfortunately, as also pointed out by them, the result depends heavily on the shape of the region, from where the points are drawn randomly. For the disc data set of size \(n\), the expected number of points left after throw-away preprocessing is bounded from below by \((1-\frac{2\sqrt{2}}{\pi})n\). Let \(r\) be the radius of the circle, in which the points lie. The preprocessing step finds (up to) eight points. Assume that the polygon determined by the found points covers the largest possible area inside the circle. Trivially, the shape that maximizes the covered area is an equal-sided octagon touching the circle at each of the vertices. Let us now consider one of the sectors defined by two consecutive vertices of such an octagon (see Figure 5). The inside angle of this sector is \(\frac{\pi}{4}\). Hence, the area of the sector is \(\frac{\pi}{8}r^{2}\). The area of the triangle inside this sector is \(\frac{1}{2}r^{2}\sin(\frac{\pi}{4})\). Since \(\sin(\frac{\pi}{4})=\frac{\sqrt{2}}{2}\), the area of the top of the sector inside the circle that is not covered (the red area in Figure 5) is \(\frac{\pi r^{2}}{8}-\frac{\sqrt{2}r^{2}}{4}\). Summing this over all eight sectors, the fraction of the circle that is not covered is \(1-\frac{2\sqrt{2}}{\pi}\). This is about \(9.968\,\%\).