Convex hull

What is the convex hull?

In geometry, the convex hull of a given set is the smallest convex set containing it. In the field of geometric algorithms, the convex hull of a finite set of points is very often used. In this case, the envelope is a convex polygon.

Incremental algorithm

Following the strategy of any incremental algorithm, this algorithm construct the convex hull of n points from the convex hull of n - 1points. Given a convex polygon (which is the convex hull of n - 1 points) and a point outside the polygon, the algorithm adds the new point as a vertex of the frontier of the new convex hull.

The algorithm proceeds as follows. First, sort the points lexicographically. Then proceed iteratively: given a point p_i and the convex hull CH_i-1 of the points p₀,...,p_i-1 , computes the supporting lines of the point p_i and the convex hull CH_i-1. Computing this supporting lines consists on finding the vertexs p_l and p_r of CH_i-1 that p_ip_l is the left supporting line of the CH_i-1 and p_ip_r is the right supporting line of CH_i-1. Then, the algorithm deletes the chain p_l,...,p_r⊂CH_i-1 and inserts the vertex p_i.

Divide and conquer

This technique consists in subdividing recursively the problem in smaller subproblems, solve them and then merge the solutions of the subproblems to get the solution of the original problem.

In the case of the convex hull, the algorithm does the following operations. First orders the points lexicographically, like in the incremental algorithm.

Then, the recurrence starts. The algorithm divides the set S of the input points into to subsets S_a and S_b such that all points in S_a precedes lexicographically those of S_b and, in addition, |S_a| + |S_b| = |S| and ||S_a| - |S_b| ≤ 1. In this way, we obtain two subsets of similar size where each convex hull are disjoined. This last property will be relevant at the merge.

The convex hull CH_a and CH_b are computed recursivelywith the two subsets S_a and S_b, respectively.

In order to merge the two convex hulls and obtain the convex hull of the set S, the algorithm computes the common exterior tangents between CH_a and CH_b. Note that the vertical separation between S_a and S_b guarantees that CH_a and CH_b that are disjoint, and, therefore, their common exterior tangents are, in fact, two, one upper and the other lower. In fact, computing them consists in finding the vertexs p^T_a, p^B_a of CH_a and p^T_b and p^B_b of CH_b such that p^T_a p^T_b defines the upper tangent and p^B_ap^B_b defines the lower tangent. The merge ends deleting the chains p^B_a,...,p^T_a ⊂ CH_a and p^B_b,...,p^T_b ⊂ CH_b and connecting p^T_a with p^T_b and p^B_a with p^B_b in order to form only one convex polligon, the convex hull of S.

Graham algorithm

This technique is also known as the gift wrapping. It consists in polygonize the set of points in a certain order and, as the polygonization progresses, gradually remove any "pockets" that may form, that is, the sub-polygons of the convex hull that are not part of the polygonization of the points that are being generated.

More specifically, first a point p is selected from the given set S, that it is certainly a point of the convex hull, taking, for example, the lexicographically minor point. Then, the rest of the points are ordered angularly from p. After that, the algorithm proceeds iteratively processing every point with the given order, and keeps at every step the convex hull of the points considered so far. For it, at the i-nth iteration, the algorithm part from the convex hull CH_i-1 of the points p,p₁,...,p_i-1. If p=v₁,...,v_k denotes the vertexs of CH_i-1, the algorithm checks if v_k-1,v_k,p_i form a left turn. If so, CH_i = CH_i-1 ∪ p_i. Otherwise, CH_i = CH_i-1 - v_k and recursively is checked again the orientation of the turn v_top-1,v_topp_i untill it is a left turn. Then, the convex hull is updated and the next point can be considered.

What are the Halton sequences?

The Halton sequences are very useful for generating random points on the plane (actually pseudo-random). This sequences are constructed with a deterministic method based on the coprime numbers. An example of constructing point in the square (0,1) X (0,1) ⊂ ℝ² with bases 2 and 3, respectively, is as follows:

To generate the sequence of base 2, the space (0,1) is divided recursively in two halves, then four parts, then eight parts, etc.

1/2, 1/4, 3/4, 1/8, 5/8, 1/16, 9/16, ...

Similraly, in base 3 the interval (0,1) is recursively divided into thirds, obtaining the sequence:

1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 1/27, ...

Combining both sequences the following points are obtained in the square (0,1) X (0,1):

(1/2,1/3), (1/4,2/3), (3/4,1/9), (1/8,4/9), (5/8, 7/9) (3/8,2/9), (1/16,5/9), (9/16,1/27), ...