Quick Hull

Algorithm

Dimension N space.
Let bd be the list of points on the boundary.
The aim is to process a list of points and find which of them is in bd.

Let a half space container be a data structure with a half space and a list of points. These points are inside or on the half space partition. Access the list of points by .L member. Access the half space by .H member.
Let cs be a stack of half space containers.

function HCpartition
(
    half space container HC,
    points list L
)
    Copy any points in L that are inside HC.H or on the boundary of HC.H to HC.L .

function createNewHC
(
    half space container HC
)
    if HC.L is empty
        return.
    Find the point p furthest from the halfspace HC.L.
    Push p to bd.
    Create N new half space containers H_i with p and N-1 points from HC.H. Each of these should not see other points in HC.H hence they all face outwards of the convex hull created.
    For each H_i
        Call function HCpartition(H_i,HC.L)

To start the algorithm find N points on the boundary/hull. Push these into bd. For example in 2D search for the furthest left and right points on the x axis. O(n) in time.

Use these initial points on the boundary to create two half space containers H₁ and H₂ that have their half spaces intersect each other at their boundaries and together partion the N dimensional space.
Let L be the list of points.
Call function HCpartition(H₁,L)
Call function HCpartition(H₂,L)
Push H₁ and H₂ onto cs.

while cs is not empty do
    pop cs to HC.
    If HC.L empty
        continue.
    Call createNewHC(HC)

Discussion

Consider the case in 2D where there are three or more colinear points at the top and the left most and right most of these are also the extremes in the set of points.

It is possible without tackling non-uniqueness that a point on the hull could be forgotten because it is colinear with two other points on the hull.

To handle this the algorithm uses copying of points (or realistically references to the points) rather than moving the points.

Better logic could improve this by moving rather than copying the points. This is better for the algorithm implementation as if we can determine uniquely which container to move which point then no automatic memory management is needed (eg copying to STL data structures).

I believe the handeling of non-unique points has lead to a robust algorithm.

Complexity

The worst case is O(n^2). The real case (when implemented) is O(nlogn). The optimal case is O(nlogn). When modified by randomizing the input of points then the expected complexity is O(nlogn) so the quick hull algorithm can be made robust.

A lot of people require guarantees on algorithms so they may reject quick hull on the ground of worst case. The worst case (which can be avoided with randomized input) is a partition where only one point is partitioned and the others are above the newly formed half spaces. This is going to happen only for a very unusual data set. For example a data set where pretty much all the data points are on or near the hull. If this is not the case then you are going to get the optimum complexity O(nlogn).

See [1] for an analysis.