The corners of a random hull

A point inside the hull of a thousand points is inside the hull of three of them, and the hull itself — the smallest convex region containing every point, the shape a rubber band takes when stretched round them — is the first object anybody computes from a scatter of data. Its corners are the extreme points, the ones that cannot be written as averages of others. The question here is how many there are when the points are random.

The answer depends on where the points were dropped, and not only on how many. Ten thousand uniform points in a triangle have about twenty hull corners; in a square, about twenty-four; in a disc, about seventy-three. Multiply the points by ten and the triangle gains about four and a half corners, the square about six, and the disc’s count more than doubles. The first two grow like the logarithm of the number of points and the third like its cube root, and the difference is entirely a matter of where the boundary bends.

Every average of the points #

A hull has two descriptions, and both matter for what follows. From the inside, it is the set of all weighted averages of the points: every point of the hull is some mixture of the scatter, with non-negative weights summing to one, which is why convexity is first met as a statement about averages. From the outside, it is what is left after cutting away every half-plane that contains none of the points, and a single straight wall separating any point outside it is the certificate that it is not in the hull. The corners belong to both descriptions: they are the points that are not averages of others, and they are the points where two of the cutting walls meet.

Computing the hull is a sorting problem in disguise. Sort the points from left to right, walk along the upper and lower chains keeping only left turns, and the corners fall out in time proportional to $n \log n$ — Ronald Graham’s scan of 1972, in the form A. M. Andrew gave it in 1979, which draws every hull on this page. The number of corners matters even to that calculation. Algorithms that are faster when the hull is small, running in time $n \log h$ for $h$ corners, were found by David Kirkpatrick and Raimund Seidel in 1986 and by Timothy Chan in 1996, and on random points in a polygon $h$ is a logarithm, so they run in time close to $n \log \log n$. How many corners a random hull has is a question about the cost of computing it as well as its shape.

Two growth laws #

Alfréd Rényi and Rolf Sulanke settled the question in 1963 and 1964, in two papers that began the probability theory of random convex bodies. For a convex polygon the average number of hull corners among $n$ uniform points is, to within a quantity that vanishes as $n$ grows,

$$\mathbb{E}[V_n] = \frac23 \sum_{\text{corners}} \left(\ln n + \gamma + \ln\frac{T_i}{A}\right),$$

where $\gamma = 0.5772\ldots$ is Euler’s constant, $A$ is the polygon’s area and $T_i$ is the area of the triangle formed by a corner and its two neighbours. Each corner of the polygon contributes two-thirds of a logarithm, and nothing else does. For a triangle, every $T_i$ is the whole area and the formula is $2(\ln n + \gamma)$; for a square, each $T_i$ is half the area and it becomes $\tfrac83(\ln n + \gamma - \ln 2)$.

For a region with a smooth boundary the law changes form. For a disc the average is about $3.383\,n^{1/3}$, the constant being $\Gamma(5/3)\,(2/3)^{1/3}\cdot 2\pi^{2/3}$, and for any smooth convex region the cube root survives with a constant built from the curvature of the boundary.

The simulations sit on the formulas across three orders of magnitude. At ten thousand points the triangle averages 19.7 corners against a formula of 19.6, the square 24.5 against 24.3, the disc 73.3 against 72.9. The polygon formulas are good even at ten points, which is unusual for an asymptotic statement; the disc’s needs a few hundred points before the cube root takes over.

These two shapes are the extremes. Imre Bárány and David Larman proved in 1988 that for every convex region in the plane the average count lies between a constant times $\ln n$ and a constant times $n^{1/3}$ — polygons at the bottom, smooth curved regions at the top, and everything else between. A logarithm grows so slowly that a polygon’s random hull never acquires many corners at all: a million points in a triangle give about twenty-nine.

Where the corners gather #

The reason for the two laws is visible in where the corners sit. Pool the hull corners of three hundred samples of two thousand points each, and the square’s gather into its own corners while the disc’s spread evenly round the edge.

A point is a corner of the hull when no other point lies beyond it, in a sense made precise by the caps of the region: the slices cut off by straight lines. Among $n$ uniform points, a cap of area much less than $1/n$ is usually empty and a cap of area much more is usually occupied, so the hull runs roughly along the boundary of the region left when every cap of area $1/n$ is removed — Bárány and Larman’s floating body. The number of corners is about the number of separate caps of area $1/n$ needed to cover the strip between the two boundaries.

On a disc, a cap of depth $h$ has width about $\sqrt h$ and area about $h^{3/2}$. Setting the area to $1/n$ gives depth $n^{-2/3}$ and width $n^{-1/3}$, and the circumference holds about $n^{1/3}$ caps of that width — the cube root. Along a straight side of a polygon a cap can be a long thin sliver of any length, so the strip along a side is covered by a few caps of enormous length and almost nothing happens there. Near a corner, where two sides meet, the caps of area $1/n$ are triangles cut off the corner at every scale from the whole polygon down to $1/n$, and the number of distinct scales is the number of factors of two between $1$ and $1/n$ — a logarithm. The figure’s crowding is the logarithm drawn: the corners of a polygon’s hull are where the polygon itself has corners, because only there does the hull have to turn.

The edge seen from every direction #

The outside description gives another way to read the two laws. In each direction $u$, the hull reaches exactly as far as the farthest point in that direction: its support function, the description of a convex shape from outside by how far it extends each way, is the largest of $n$ random projections. The region’s own support function is the largest projection anything inside could have, and the gap between them is how far the hull falls short in that direction.

That gap is an extreme-value question, of the same kind as how long the longest run of heads in a long sequence of tosses is: the maximum of many independent quantities, governed by how much probability sits near the top. For a disc, the share of points within $h$ of the edge in a given direction is a cap of area about $h^{3/2}$, so the gap is about $n^{-2/3}$. For a square looked at straight across one side, the share within $h$ of that side is a strip of area $h$, and the gap is about $1/n$ — much smaller. A polygon’s random hull is thus extremely close to the polygon’s sides and noticeably short only at its corners, while a disc’s hull falls short evenly all the way round. The corner counts and the gaps are the same fact.

Corners counted by the area left out #

There is a second quantity in the picture, the area of the region the hull fails to cover, and in 1965 Bradley Efron showed that it is not a second quantity at all.

Efron’s argument is three lines. Draw $n$ points and ask whether the last of them is a corner of the hull of all $n$. It is a corner exactly when it falls outside the hull of the other $n - 1$ — and since it is uniform and independent of them, the chance of that is the average share of the region those $n - 1$ points leave uncovered. Every point is equally likely to have been last, so the average number of corners is $n$ times that chance:

$$\mathbb{E}[V_n] = n\left(1 - \frac{\mathbb{E}[A_{n-1}]}{A}\right).$$

The figure checks it at every size, for both shapes. Its consequence is that every statement about corners is a statement about missed area: the triangle’s $2\ln n$ corners mean that its random hull misses about $2\ln n / n$ of the triangle, and the disc’s $3.383\,n^{1/3}$ corners mean it misses about $3.383\,n^{-2/3}$ of the disc. The disc is covered less well, by a larger margin than the corner counts suggest, because a curved boundary leaves a thin crescent all the way round.

The perimeter can be read the same way. A convex curve’s length is the average of its widths in every direction, times π, so the hull’s perimeter falls short of the region’s by the average of the gaps just described: by about $\ln n / n$ for a polygon and about $n^{-2/3}$ for a disc. Area, perimeter and corners all carry the same exponent for each shape, because each is a sum over the same caps.

The same Efron spent much of his career on the opposite question, of how many kinds a sample has not yet seen, and the hull identity has the same spirit: a quantity that looks like it needs the whole configuration is read off one point at a time, by asking what that point adds.

When every point is a corner #

At the other extreme, all $n$ points might be corners — in convex position, with none inside the hull of the rest. For four points this is a famous question. James Joseph Sylvester asked in 1864 for the chance that four random points form a convex quadrilateral, received different answers from different correspondents, and realised that the question has no answer until it says where the points are drawn from.

Sylvester’s question sits in the oldest tradition of geometric probability, the one that began with Buffon dropping needles on a ruled floor, and its lack of a single answer was one of the episodes that taught the subject to say what uniform means before computing anything.

For four points in a square the chance is $25/36$, in a triangle $2/3$, and in a disc $1 - 35/(12\pi^2) \approx 0.7045$. Wilhelm Blaschke proved in 1917 that these are the extremes: no convex region gives four points a smaller chance of convex position than a triangle, and none a larger chance than a disc — or an ellipse, which is a disc seen at an angle and gives the same answer, since stretching the plane changes no question about convexity.

For more points the chance falls fast, and in 1995 and 1996 Pavel Valtr found it exactly for the square and the triangle:

$$p_n^{\square} = \left(\frac{1}{n!}\binom{2n-2}{n-1}\right)^2, \qquad p_n^{\triangle} = \frac{2^n\,(3n-3)!}{(n-1)!^3\,(2n)!}.$$

The square’s formula is a square because Valtr’s proof treats the two coordinates separately, and each contributes the same factor. At eight points the chance is 0.72 per cent in a square and 0.49 per cent in a triangle, and the simulation matches both formulas within its sampling error. For the disc nothing so simple is known beyond four points.

The four-point question has a life far from probability. The fewest crossings a straight-line drawing of a complete graph can have is governed by a constant that Edward Scheinerman and Herbert Wilf showed in 1994 to be the smallest chance, over every way of choosing random points in the plane, that four of them are in convex position — because four points in convex position force exactly one crossing, between the two diagonals of their quadrilateral, and four points not in convex position force none. Blaschke’s triangle bound is a bound on drawings of graphs.

Peeling the hull away #

The hull is the outermost layer of a scatter. Remove its corners and take the hull of what is left, then remove those, and continue until nothing remains: the scatter comes apart like an onion into nested convex layers.

The number of layers grows like $n^{2/3}$ — the measured slope between three hundred and ten thousand points is 0.667 — and Ketan Dalal proved in 2004 that this is the right order for uniform points in a disc; the square behaves the same way here. The exponent is not the hull’s: the first layer of a square has a logarithm’s worth of corners, but each later layer is the hull of points that are no longer uniform, because the earlier peelings have removed the outermost ones, and the layers deeper inside look more and more like hulls of points in a rounded region. Five hundred points give thirty-two layers with between fifteen and twenty-five corners each, not the eleven the first-layer formula would give every time.

Peeling has a statistical use. The innermost layer is a natural notion of the middle of a scatter in two dimensions, where there is no ordering to take a median from; the idea of peeling a scatter’s hulls to find its middle goes back to John Tukey in the 1970s, and the result is resistant to outliers in the way a median is and an average is not. The two-dimensional median it gives behaves like the median of a list of numbers, unmoved by a few wild values at the edge, because those are peeled away first. A point’s layer number is how deep it sits, and the $n^{2/3}$ law says how fine that measurement is.

What the averages do not show #

Every curve here is an average, and the averages hide spread. The number of corners of a random hull in a square has variance growing like $\ln n$ as well, so at ten thousand points a single sample often has eighteen corners, or thirty. Rényi and Sulanke’s formulas say what happens on average, and the figures confirm only that.

The formulas are also limits. That the square’s simulated counts agree with $\tfrac83(\ln n + \gamma - \ln 2)$ to a tenth of a corner from a hundred points upwards is a fact about these simulations and a sign that the neglected terms are small; it is not a bound on them. And the figure of where the corners gather shows one scale. The logarithm says that corners are found at every scale near a polygon’s corner, from the whole polygon down to $1/n$, and a picture of two thousand points shows only the coarsest few of them.

Finally, Efron’s identity and Valtr’s formulas are exact, and the simulations are checks on arithmetic rather than evidence for theorems. The disc’s chances of convex position beyond four points are the one set of numbers here that are measured and not derived, and their last digits are uncertain by the sampling error of two hundred thousand trials.

Still open: the worst region in three dimensions #

Blaschke’s two extremes for four points in the plane have analogues in space. In three dimensions the question is the chance that five random points in a convex body are in convex position, which is the chance that none falls inside the tetrahedron of the other four. Helmut Groemer proved in 1973 that ellipsoids give the largest chance, in every dimension, extending Blaschke’s disc. Which body gives the smallest chance is not known. The natural guess is the tetrahedron, extending Blaschke’s triangle, and it is called the simplex conjecture. It has been open for half a century, and the methods that settle the plane — symmetrisation, sliding the region’s boundary until it becomes a triangle without increasing the chance — do not keep the probability monotone in higher dimensions.

A count set by the bends of a boundary #

The number of corners of a random hull is set by where its region bends. A polygon bends only at its own corners, and there the hull turns through a logarithm’s worth of scales, two-thirds of $\ln n$ for each; a smooth region bends everywhere, and the hull turns through about $n^{1/3}$ caps all the way round. Efron’s identity turns that count into the area the hull misses, Valtr’s formulas give the extreme case of every point a corner, and the layers beneath the hull grow like $n^{2/3}$. Three exponents — nought with a logarithm, one-third and two-thirds — describe the outline of a random scatter completely enough to be checked to a tenth of a corner.