Skip to main content
MathOverflow

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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

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

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

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

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