A convex hull is the smallest convex polygon that encloses a set of points. Imagine stretching a rubber band around the outermost points: when released, it forms the boundary, while interior points remain inside. section 11.3.3
The hull is an ordered sequence of selected input points, and it may contain fewer points than the original set. A valid result encloses every point and uses the minimized outer boundary rather than cutting across the set or taking unnecessary detours. section 11.3.3
When treated as a sequential machine-learning problem:
- An encoder RNN converts the input coordinates into a representation. section 11.9
- A decoder applies content-based attention over the input points. section 11.9
- A softmax distribution assigns probabilities to input positions, allowing the model to point to the next hull vertex. section 11.9
A learned hull for 50 points
A ConvexNet model predicts an ordered list of hull indices from a generated 50-point sample. In one displayed case, the predicted and true index sequences match exactly, producing 100% hull overlap; SciPy's ConvexHull provides the comparison.
