Projection of a point to a convex hull in d dimensions

Question

Hi,

I've got n points in d dimensions (typically n is around 30k-60k and d is 5 or 6). I'm using qhull to calculate the Delaunay triangulation and the convex hull of the set of points.

You can assume each point was drawn from the normal multidimensional distribution. I need the triangulation for function interpolation which works quite well once you calculate the simplex/barycentric coordinates of the query point p.

The problem is how to handle points that are outside the convex hull (which occurs fairly infrequently - but does occur)? I need a way to project the point onto the hull's surface and calculate where on the d-1 dimensional face it hit so that I can interpolate this point (essentially clipping the point to the region of the hull).

Is there an efficient algorithm out there that does this? I came across this on the web but am not clear how to apply it across the entire hull efficiently.

Thanks

Answer 1

The natural projection of your exterior point $a$ is to the point $b$ on the polytope that is closest to $a$, i.e., which minimizes the distance $|ab|$. This can be formulated as a quadratic programming problem, for which there are many algorithms.

Quite some time ago, Gilbert worked out some methods:

(1) E. G. Gilbert, "Minimizing the quadratic form on a convex set", SIAM J. Contr., vol. 4, pp.61-79 1966

(2) E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, "A fast procedure for computing the distance between complex objects in three dimensional space", IEEE J. Robot. Automat., vol. 4, pp.193-203 1988 (PDF link)

The first sentence of the 2nd paper above is: "An efficient and reliable algorithm for computing the Euclidean distance between a pair of convex sets in $\mathbb{R}^m$ is described." This algorithm has become known as the GJK algorithm.

I doubt this is the last word on the topic. There is a huge literature on collision detection in $\mathbb{R}^3$—which often amounts to finding the minimum distance from a point to a polyhedron—but I don't know how much of it scales gracefully to dimensions $5$ or $6$.

Answer 2

I found a very simple algorithm that returns the barycentric coordinates of an arbitrary point in n dimensions - so what I've done is to find all the outermost simplexes (in qhull you just check that at least 1 entry in the neighbours list is -1) - and by brute force check the distance from the query point (in each simplexes barycentric coordinates) to the simplex's projection and pick the smallest one.