Is there a way to further optimize Graham Scan algorithm to find the convex hull?

Question

I went through chan's algorithm. It doesn't seem much better to me. Is there a way I can replace that sorting part in graham scan with anything else ? so that O(nlogn) time could be further reduced. Java implementation is preferred.

Answer 1

The best way to optimise the sorting step is to avoid considering points which will not be part of the convex hull. This is called Akl-Toussaint heuristic http://www-cgrl.cs.mcgill.ca/~godfried/publications/fast.convex.hull.algorithm.pdf. You can quickly scan through all vertices and find a quadrilateral formed the pointset (you can get the four points as the extrema of for all vertices in ±(x+y), ±(x-y)), then just delete all the vertices inside this quadrilateral.

After this you can use Graham's scan or Andrew's monotone chain algorithm —my favourite, both are of O(n log n)complexity. Note that, like @Chill mentioned in comments above, Chan's method is optimal.

In practice this method is much faster than applying one of the algorithms to the point set without any filtering.

The paper I linked above mentions a "throw-away" idea in the conclusions section. This is a slight improvement, since we can throw away most of the vertices while searching for the quadrilateral itself. I am attaching a snippet just for this heuristic.

/**
 * Given verts: Array(Points).
 */

/*
 * if we have more than 100 points use Akl-Toussaint heuristic to remove
 *  points that we know are surely not part of the hull.
 * S.G. Akl & Godfried Toussaint, 1977,  "A Fast Convex-hull Algorithm"
 */
if (verts.length > 100) {
    var min = Math.min,
        max = Math.max;
    var minU = minL = maxU = maxL = verts[0];
    var minUval = minU.x - minU.y;
    var minLval = minL.x + minL.y;
    var maxUval = maxU.x + maxU.y;
    var maxLval = maxL.x - maxL.y;
    var xMin = yMin = xMax = yMax = 0;
    var vertList = [];
    for (i = 0 ; i < verts.length; ++i) {
        var v = verts[i];
        var x = v.x;
        var y = v.y;
        if (!(x > xMin && x < xMax && y > yMin && y < yMax)) {
            vertList.push(v);
            var sum = x + y;
            var diff = x - y;
            if (diff < minUval) minU = v;
            if (diff > maxLval) maxL = v;
            if (sum < minLval) minL = v;
            if (sum > maxUval) maxU = v;
            minUval = minU.x - minU.y;
            maxLval = maxL.x - maxL.y;
            minLval = minL.x + minL.y;
            maxUval = maxU.x + maxU.y;
            xMin = max(minU.x, minL.x);
            yMin = max(minL.y, maxL.y);
            xMax = min(maxU.x, maxL.x);
            yMax = min(minU.y, maxU.y);
        }
    }

    // reset the vert's array, and do one more filtering pass 
    // on vertList
    verts.length = 0;
    for (i = 0 ; i < vertList.length; ++i) {
        var v = vertList[i];
        var x = v.x;
        var y = v.y;
        if (!(x > xMin && x < xMax && y > yMin && y < yMax))
            verts.push(v);
    }
    // verts now only contains a subset of vertices.
}
// Run a convexhull algorithm on verts.
// ...