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](https://sites.cs.ucsb.edu/%7Esuri/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?



Example of worst case distributions for 4D convex hull
I'm making my comment an answer so this doesn't appear on unanswered lists.


The convex hull of points on the [moment curve](https://en.wikipedia.org/wiki/Moment_curve)
$$
(t, t^2, t^3, t^4)
$$
form what is known as a [cyclic polytope](https://en.wikipedia.org/wiki/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.


