What is Convex Hull? Where is it used?

What you need to know

The convex hull of some points is the smallest convex set containing them all. In 2D it is a polygon whose corners are some of the original points. Picture pins on a board and a rubber band snapped around them: the band's shape is the hull.

Linear separability

Two classes are linearly separable if one straight line (in 2D) or hyperplane (in more dimensions) puts all of class A on one side and all of class B on the other. For a finite set of points, this is true exactly when the two classes' convex hulls do not intersect.

XOR shows the failure:

x1  x2  XOR0   0   00   1   11   0   11   1   0

Class 0 is the points (0,0) and (1,1); their hull is the diagonal line between them. Class 1 is (0,1) and (1,0); their hull is the other diagonal. The two diagonals cross at (0.5, 0.5), so no single line can separate them. A single-layer perceptron draws exactly one line, so it cannot learn XOR. A hidden layer fixes this by moving the points into a new space where the hulls no longer overlap.

Hard-margin SVMs

For linearly separable data, the hard-margin SVM boundary is the perpendicular bisector of the shortest line between the two classes' hulls. The support vectors are points on the hull boundaries. This gives a geometric picture of "maximum margin".

Other uses

• Computer vision — shape analysis, finding the outline of a hand or object (OpenCV's cv2.convexHull), detecting convexity defects such as the gaps between fingers.
• Robotics and games — fast collision checks use hulls of objects.
• Optimisation — a convex problem has one global minimum. Neural network losses are not convex, which is why training can stall in poor regions.

A real-life example

A factory camera checks cashew nuts on a conveyor belt. The system segments each nut, computes the contour's convex hull, and compares the contour's area with the hull's area. A whole nut fills about 95% of its hull. A broken nut has a big bite missing, so it fills only 75–80%. Nuts below 88% are pushed off the belt by an air jet. This is a simple, explainable rule that runs in microseconds, before any neural network is needed.

In ML terms: a credit-card fraud team plots two features and sees fraud and normal points overlap heavily. Their hulls intersect, so no linear model on those two features can separate them perfectly. That is a signal to add features or use a non-linear model.

Follow-up questions to expect

• "How is the convex hull computed?" — Algorithms like Graham scan or Andrew's monotone chain run in O(n log n) in 2D. In practice you call scipy.spatial.ConvexHull or OpenCV.
• "Why do we care that the loss surface is not convex?" — Gradient descent can only promise a local minimum on a non-convex surface. In large networks most local minima are good enough, but saddle points and flat regions slow training.
• "How does a hidden layer solve XOR?" — It maps the four points into a new feature space where the two classes become linearly separable, then the output neuron draws one line there.