Skip to main content
2 of 2
Commonmark migration

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$.

Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958