I want to measure "how convex" a set of points $x_n\in\mathbb R^K, n=1\ldots N$ is. Both $K$ and $N$ are potentially large $N\gtrsim 10^6$, $K\gtrsim 10^3$.
One way would be to compute the volume of the convex hull spanned by these points, but I do not know about any scalable algorithm to compute this quantity.
Are there any efficiently computable scalars that measure convexity of point clouds?
EDIT: I guess a different way to define a measure of "how far" a set is away from being convex would be something along the lines of optimal transport, i.e. measuring the minimal amount of volume that would need to be moved (and how far) to make the set convex (analogous to the Wasserstein metric). Again it is unclear if and how one could translate this definition into a scalable program that computes it.
EDIT 2: I already tried using Qhull but it just doesn't seem scalable enough for the task. Again I would be happy to use some crude approximation / proxy if it is able to deal with large amounts of data.
Ok so doing some more literature search I found this Simulated annealing in convex bodies and an $\mathcal O^*(n^4)$ volume algorithm. The algorithm requires that one has access to an oracle, a black box function that can tell whether a point is inside the body or not, which I think I can provide in my application.
In this survey they are able to estimate the volume for $K=100$, $N=200$ in 20min and for a dataset with $K=14$, $N=16000$ in 1min using a single Intel Core i5-2400. Guess I'll try my luck with that.