Effect of the curse of dimension on collision detection

Question

I require a crude intersection analyzer or collision detector in about 15 dimensions. I am wondering if such a function is rendered difficult or impossible by the "curse of dimension". Collision detectors are widely used in 2 and 3 dimensions to determine if two shapes are in contact. A function that determines the intersection of two regions is one way to make a collision detector. The "curse of dimension" refers to difficulties encountered as the number of dimensions involved increases beyond about 5. For example, all points tend to be clustered near hyper-surfaces, and, statistically, all points behave like outliers. (See the Encyclopedia of Mathematics.) I haven't been able to find any literature on such collision detectors beyond 4 dimensions, and I would appreciate being pointed in the right (best?) direction.

Answer 1

An overview of high-dimensional collision detection for the purpose of motion planning is in Petrović - Motion planning in high-dimensional spaces:

Grid-based approaches are resolution complete and often offer optimal solutions. However, the number of grid points grows exponentially in the configuration space dimension, which makes even the state-of-the-art methods inappropriate for very high-dimensional problems. Sampling-based approaches are efficient in most practical problems but offer weaker guarantees. They are probabilistically complete, however, they often require post-processing and can still be inefficient in very complex configuration spaces. Trajectory optimization approaches can solve high-dimensional motion planning problems quickly, but solutions are only locally optimal.

Answer 2

If your objects fit into ellipsoids, then one option might be the Perram-Wertheim distance; in dimension $n$ you do need to invert an $n \times n$ matrix, which might be do-able ...