GJK implementation

Basic use cases

Given two sets of points in nd (possibly lifted from a 2d space):

1. separation problem: are they linearly separable ?
2. distance problem: they are separable, but how far they are from each other ?

Sketch of the algorithm

Let X1 and X2, two sets of points in nd, of size m1 and m2. The set difference is denoted by X = X1 - X2. Then: dist(X1, X2) = dist(X,o), where o is the origin. To compute dist(X,o), the idea is to generate a sequence of polytope Vk contained in conv(X) (having at most n+1 affinely independent points), such that dist(Vk,o) converges towards (and reaches) dist(X,o):

1. k = 0, Vk has v points in X (1 <= v <= n+1).
2. if Vk contains o, then stop, else go to 3.
3. find V'k in Vk, which must be the closest polytope to o (of at most n affinely independent points).
4. set Vk+1 to V'k U farthest( normal( V'k ) ), k++, go to 2.

NB: in 4. farthest( normal( V'k ) ) returns one of the points in X, which are the farthest along the direction normal to V'k (affine subspace of dimension at most m-1). This can be computed in O(m1+m2) from points of X1 and X2 by determinant computations (or even determinant sign evaluations).

NB: Most difficult tasks are 2. and 3.

on-line version

required operations

At least determinant computation (or determinant signs computation)