Quick Shell Algorithm

The set of points is divided into two subsets, each of which will contain one of the broken lines, the connection of which gives a polygon of a convex hull.

1. We take two extreme points of the set S - the left A and the right P. Draw a straight line through them. We denote by S1 the subset of points located above or on a straight line passing through points A and P, and by S2 the subset of points located below or on the same straight line.
2. Consider the upper subset S1. Choose the point Pi that has the greatest distance from the line LP (the triangle LPiP has the largest area). If there are several such points, choose the one with the largest PiLP angle. The point Pi is the vertex of the convex hull of the set. In fact, if a straight line parallel to the line of the LP is drawn through the point Pi, then there will not be a single point of the set S above this line. Perhaps other points will appear on the constructed line, but, according to the choice made, Pi is the leftmost one. T. about. The point Pi cannot be represented by the convex combination of two other points of the set S. We construct the lines ЛPi and PiП. Points located to the right of both lines can be excluded from further consideration, since they are internal points of the triangle ЛПiП, that is, they do not belong to CH (S) - the boundary of the convex hull.
3. Now we consider a subset of points S11 located to the left of or on the line ЛПi, and a subset of points S12 located to the left of or on the line ПИП. For each of the subsets we construct a convex hull. The convex hull of the set S1 is formed by gluing together the ordered lists of vertices CH (S11) and CH (S12).
4. We solve the problem for S2.

The complexity of the algorithm consists of the complexity of constructing two subsets of the set O (N) under consideration and the difficulties of solving subproblems for each of the subsets: T (N) = T (a) + T (b) + O (N).

In the best case, when the task is divided into two equally powerful subtasks, the complexity of the algorithm is the solution of the recursive equation:

(1) T (N) = 2 T (N / 2) + O (N) =>

(2) T (N) = O (N log N).

At worst:

(3) T (N) = T (1) + T (N 1) + O (N) =>

(4) T (N) = O (N2).

Lemma The solution to equation (1) is function (2). Let N = 2k. Then T (2k) = 2 T (2k 1) + C 2k; T (2k 1) = 2 T (2k 2) + C 2k 1 => T (2k) = 4 T (2k 2) + 2 ° C 2k 1 + C 2k = 4 T (2k 2) + 2 ° C 2k => T (2k) = 2m T (2k m) + m С 2k For m = k (= logN), the algorithm ends: T (N) = NT (1) + C logN N = O (N logN)

• Graham Algorithm
• Jarvis Algorithm
• Chan Algorithm

• C ++ implementation
• [1]