Real-Time Physics Simulation Forum

Here are a few questions about Johnson's Distance Algorithm based on Gino's book:

1) How do you choose y_k ? Is it the closest point to the origin ?

2) The cofactors used in the summation ( delta_ix ) are taken from the matrix based on all points from Y ( non-reduced simplex ) or are they taken from the matrix based on points of X ( reduced simplex ) at the moment of j-th iteration ?

3) At each j-th iteration a point is added or not to X depending on the delta_j(x+y_j) value, right ?

Thank you!

1) There are two options: (a) choose y_k arbitrary or (b) choose y_k such that y_k - y_j is the shortest. The latter choice is numerically stabler, but also more expensive. See book for details.

2) Both. Matrices for reduced simplices are minors of the current simplex' matrix. A determinant of a matrix is computed recursively by adding and subtracting determinants of its minors. If you are having trouble with this then you might want to review

http://mathworld.wolfram.com/Determinan ... inors.html

3) No. In each iteration, all subsimplices (or at least the ones that contain the last found support point) are evaluated. Points are always added before evaluation. Points that are not on the closest subsimplex are removed. In theory, any newly added point should survive at least the next evaluation, i.e. the new simplex should contain the last found support point. (If only machinery would answer to theory.)

Hope this helps,

Gino