The paper gives the following definition, which is pretty much a constructive one:
- Linear interpolation is used between adjacent points.
- No point lies above the final curve.
- For any pair of points used to construct the curve, the line segment connecting them is equal to or below the curve.
The main problem with this one is it's not a particularly intuitive thing.
So let's look at Wikipedia:
Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X.
This is pretty good, and carries some intuition, but (unless you have experience of convex sets) doesn't really give much of an idea of what it's like.
It also gives the commonly used (and intuitive) "rubber band" explanation of a convex hull:
For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X
This intuitive explanation must be slightly modified for ROC curves, because of the way they're defined - the convex hull of an ROC fulfill the conditions for an ROC. So if we take a stretched "rubber band" which is fixed at (0,0) and (1,1) and the middle is pulled up and to the left so that it sits "outside" (0,1), and release it so that it "catches" on the points, then between (0,0) and (1,1) the rubber band will form the convex hull of the ROC:
Hopefully, now, the intent of the definitions should be clearer.