Given a set of points, a convex hull of those points is the smallest possible convex polygon that contains all the points.

Finding a convex hull given a set of points is just one of the many topics covered by an area of Computer Science called computational geometry.

Graham's Scan is an efficient algorithm to find the convex hull of a set of points. In fact asymptotically, you cannot do better than Graham's Scan which has a time complexity of O(n log n). This is because the the problem of sorting can be reduced to the convex hull problem. And as we all know, sorting is O(n log n).

In equivalent but more mathematical terms, the convex hull of a set of points S (in some vector space over the real numbers or other field of characteristic 0) is the "smallest" convex set containing S. Such a set exists: the intersection of a family of convex sets is itself convex, so the convex hull of S is merely the intersection of all convex sets containing S.

Equivalently, since every convex set is the intersection of half spaces, the convex hull of S is the intersection of all half spaces containing S.

Log in or register to write something here or to contact authors.