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).