Example of worst case distributions for 4D convex hull

Question

My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf

This same source writes

In 4D, there are n points in general position so that the edge joining every pair of points is on the convex hull!

But I can't seem to demonstrate this in practice. I tried the follow distributions of points:

• Gaussian distribution (e.g., V = randn(n,4))
• Uniform distribution in box (e.g., V = rand(n,4))
• Uniform distribution on 3-sphere (e.g., V=normalize_each(randn(n,4));)

The 3-sphere lead to the worst number of edges but it still empirically looks linear as I increase n.

Is there a known pathological distribution of points that really hits this quadratic behavior as n increases?

Answer 1

I'm making my comment an answer so this doesn't appear on unanswered lists.

The convex hull of points on the moment curve $$ (t, t^2, t^3, t^4) $$ form what is known as a cyclic polytope. This is a "neighborly polytope" with the property (in this case with $d=4$) that every pair of vertices is connected by an edge.