  Achieving completeness in the motion planning problem demands substantial
computation power, especially in high dimensions. Recent developments in
parallel computing have rendered this more achievable. We introduce an
embarrassingly parallel algorithm for constructing infeasibility proofs.
Specifically, we design and implement a manifold triangulation algorithm on
GPUs based on manifold tracing with Coxeter triangulation. To address the
challenge of extensive memory usage within limited GPU memory resources during
triangulation, we introduce batch triangulation as part of our design. The
algorithm provides two orders of magnitude speed-up compared to the previous
method for constructing infeasibility proofs. The resulting asymptotically
complete motion planning algorithm effectively leverages the computational
capabilities of both CPU and GPU architectures and maintains minimum data
transfer between the two parts. We perform experiments on 5-DoF and 6-Dof
manipulator scenes.
