- linear programming
L is planar equation L(p) = N.p - d where N = [x,y,z] and d are unknowns
find x,y,z,d such that:
for all vertices v of O1, L(v) < 0
for all vertices w of O2, L(w) < 0
- Minkowski sum
the minimum separation distance between two objects
is the same as the minimum distance from the origin
of the Minkowski sums of A and -B to the surface of
the sums.
- Voronoi diagrams (induced by convex polytope)
precompute the external Voronoi region for each polytope
at each time step, check if a pair of features is inside of
other's Voronoi region
perform a local walk on surface of object until if finds
the closest features
when high motion coherence, local walk near 'constant time'
several optimizations have been presented in the literature
- Kinetic Data Structures (KDS)
Recently presented in the lit.
keeps track of closest features during motion
performance is separation sensitive and may depend on
min. distance relative to size.
includes linear motion, translation along an algebraic
trajectory, or algebraic rigid motion