The Shape Decides
The convex hull of n random points has far fewer than n vertices. How many fewer depends on the shape they came from, not on n.
What it is
Points accumulate in a square on the left and a disc on the right, twenty up to four thousand, and each panel keeps its convex hull drawn. Below, both hull sizes plotted against point count on a log axis. Tap to hold.
Same algorithm both sides. Same number of points at every instant. The hulls don’t stay comparable.
How it works
Andrew’s monotone chain. Sort by x, sweep left to right keeping only points that turn the right way, sweep back for the other half. Anything that fails the turn test was inside the hull and gets popped. O(n log n), dominated by the sort.
Measuring growth is just running that a lot of times and averaging, then fitting two
candidate models, a + b·log n and a + b·n^(1/3), and comparing residuals.
What surprised me
Both shapes look the same when you draw the points. They don’t behave the same at all, and the difference isn’t a constant factor, it’s a different growth class.
Mean hull size over 120 trials each:
| points | square | disc |
|---|---|---|
| 50 | 10.0 | 11.7 |
| 200 | 13.9 | 19.2 |
| 800 | 17.4 | 31.0 |
| 3200 | 21.6 | 49.0 |
| 6400 | 23.4 | 62.9 |
Fitting both models to both datasets:
| log n residual | n^(1/3) residual | |
|---|---|---|
| square | 0.26 | 0.85 |
| disc | 3.66 | 0.30 |
Each shape prefers its own model by an order of magnitude in residual. The square’s fitted slope against log n comes out at 2.739 where theory says 8/3 = 2.667. Two and a half percent off, from a Monte Carlo with no fitted constants beyond the two the line needs.
Why the shapes differ took me a while to see. It’s the corners.
A square’s hull is pinned by four of them. Adding points mostly finds slightly better candidates near those same four places, and “slightly better” is a logarithmic business. A disc has no corners to be pinned by, so every new point on the boundary is a genuinely new direction and the hull keeps gaining vertices at a polynomial rate.
That’s a fact about the boundary’s curvature, not about the points. Zero curvature almost everywhere plus four singular corners gives log n. Uniform positive curvature gives n^(1/3). At 6400 points the disc’s hull has 2.7 times as many vertices as the square’s, and the gap widens forever.
I’d assumed convex hull cost was a story about n. It’s at least as much a story about what the points came out of.
What I would do next
Interpolate. A rounded square with the corner radius as a dial. The growth exponent has to move continuously from log n to n^(1/3) as the corners round off, and I want to see what it does in between.