Number of layers in nested convex hull

Question

Find the maximum number of nested convex hull

Answer 1

The minimum number of layers is clearly $1$, which happens iff all your points are extreme points (for instance, when they are all on a circle).

The maximum number of layers is probably $\lceil n/3\rceil$, which happens when you have nested triangles.

This bound is for the plane. In dimension $d$, it should be $d+1$ instead of $3$.

Answer 2

Hint:

• The convex hull of $n$ points in general position in $d$-dimensional space may have from $(d+1)$ to $n$ vertices.
• The convex hull of points in non-general position may have only $2$ vertices even in high dimensions (it may have 1, but there won't be any layers then).
• In $\mathbb{R}^d$, as long as your convex hull has non-empty interior, whatever figure you have, you can scale it down so that it fits strictly inside (i.e. it doesn't even "touch" the boundary of the hull).

I hope it helps $\ddot\smile$

Answer 3

Here's a worst-case example, and it occurs in dimension 1. your set of $n$ points has $n$ odd, $n = 2k + 1$. The points are at position $-k, -k + 1, \ldots, -1, 0, 1, 2, \ldots k$ on the $x$-axis.

The first convex hull consists of the points at $-k$ and $k$; the next consists of points at $-k + 1$ and $k-1$, and so on. The total number of hulls: $k + 1 = \frac{n+1}{2}$.

You can generalize this to $p$ dimensions -- place all the points on the $x$-axis in a higher-dimensional space. This is clearly a degenerate case -- usually points don't all lie on a line! -- but it's still one you have to consider. On the other hand, whether this example "works" depends on your definition.

I say "depending on definition" because in this example, the inner $n-2$ points may or may not be considered as part of the "hull". If you want to consider them part of the hull, and you're working in the plane, then the previous answer is good: roughly $n/3$ sequential hulls, and you'd better round up just to be safe (think of a triangle with a point at its center!).