Oranges in Many Dimensions
Peeling oranges in high dimensionality is hard. This post discusses a fundamental phenomenon in asymptotic geometry and explains at which rate you should peel an orange.
Suppose we have a special branch of hyper-orange existing in and we would like to peel such that of pulp is preserved. We will denote the volume of an norm in dimensions, that is , as . Because we first deal with balls we have and set by default .
We first look at ratios of volume of balls radii scaled by such that . For we know from middle school that , and , and hence . For we need some material from real analysis to work out the volume.
Volume of n-ball Exponential Function
One proof works with two observations: first scaling area identity and evaluates the integral for rotational invariant function .
On the one side, we have
On the other side, isolating one variable and applying the area identity
Solving for the dimensional area we get and substituting into the volume formula, we get the desired .
Consequence for Peeling Oranges
Now consider the volume of two balls , and compare their volume
Then, for every constant the ratio tends to zero, and we are left with no pulp at all! Realizing that for , the limit yields exponential function
we should peel of the skin to get a fair share of pulp for high dimensions.
Consequence for Approximating Norms
Let’s pack the orange into a box. For simplicity we assume that the box has side length and recognize that an -cube is described with the maximum norm. The volume of such a box is , and comparing that to the volume of our orange
Express this in log-space and use log-gamma approximation
which turns negative once and grows linear in the dimensionality. Hence, the fraction diminishes exponentially fast. That means for large we can pack exponential many oranges into a single box!