11
$\begingroup$

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.

$\endgroup$
0
11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Excellent, thanks! $\endgroup$ Jul 25 at 17:21
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yes, I'll always be on machines with programmable GPUs, and matrix inversion is one of their strengths. Thanks, this is just what I need. $\endgroup$ Jul 25 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.