# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 2 Preliminaries
### Robustness  
In [PERSON] experiments [PERSON] (2014), the coordinates of the points were floating-point numbers. It is well-known that the use of the floating-point arithmetic in the implementation of the basic geometric primitives may lead to disasters (for some classroom examples--one being the computation of the convex hulls in the plane, we refer to [17]). Therefore, it was somewhat surprising that the robustness issue was not discussed at all. Given the floating-point setting, the programs used in [PERSON] study [PERSON] (2014), as well in some other experimental studies (see, for instance, [18; 19]), are only able to compute an uncontrolled approximation of the convex hull. The output polygon may not even be convex, it may miss some of the convex-hull vertices, and it may contain some interior points--in an uncontrolled away.  
The _orientation test_ is a basic primitive that is used in many geometric algorithms. It takes three points \(p\), \(q\), and \(r\), and tells whether there is a left turn, right turn, or neither of these at \(q\) when moving from \(p\) to \(r\) via \(q\). This primitive can be seen as a special cross-product computation, and it is a known improvement used to avoid trigonometric functions and division.  
Recall that an _overflow_ means that the result of an arithmetic operation is too large or too small to be correctly represented in the target variable ([20], Section 2-13). In our experiments we rely on the exact-arithmetic paradigm. The coordinates of the points are assumed to be integers of fixed width, and intermediate calculations are carried out with integers of higher precision so that all overflows are avoided. When computing convex hulls in the plane, it is easy to predict the maximum precision needed in the intermediate calculations. A construction of a signed value from an unsigned one may increase the length of the representation by one bit, every addition or subtraction may increase the needed precision by one bit, and every multiplication at most doubles the needed precision.  
For points \(p=(p.x,p.y)\), \(q=(q.x,q.y)\), and \(r=(r.x,r.y)\), we treat their _cross product_ as a single number \((q.x-p.x)(r.y-p.y)-(r.x-p.x)(q.y-p.y)\). If the cross product is positive, there is a left turn at \(q\) when moving from \(p\) to \(r\) via \(q\). If the cross product is negative, there is a right turn. Additionally, if it is 0, the points are collinear. The cross product measures the (signed) area of the parallelogram spanned by the oriented line segments \(\overrightarrow{pq}\) and \(\overrightarrow{p\hat{r}}\). So the cross product can also be used to determine which point \(r\) is farthest from the line segment \(\overrightarrow{pq}\) (above or below).  
Let us consider how the left-turn orientation predicate can be coded in C++. The code for the right-turn, no-turn, and signed-area calculations is similar. Using the off-the-shelf tools available at the CPH MPL [21] and the CPH STL [22], the C++ code for computing the left-turn predicate is shown in Figure 1. If the width of the original coordinates is \(\mathtt{w}\) bits, with \((2\mathtt{w}+4)\)-bit intermediate precision we can be sure that no overflows happen--and the computed answer is correct. There are many other--more advanced--methods to make this computation robust (for a survey, we refer to [23]).  
One left-turn test involves two multiplications, four subtractions, six constructor calls, and one comparison. When the numbers are wider than any of the built-in integers, we have to operate on double-word (cphst1::Z<68>) or triple-word integers (cphst1::Z<132>). This makes the arithmetic operations even more costly. Hence, the goal to reduce the number of times the geometric primitives are to be executed is well motivated.