Simplex with smallest possible total edge length in set of points

Solution 1:

I am not sure I understand all the details of the problem you are attempting to solve. But, since nobody else has answered, here's an idea...

Perhaps you could speed up processing using something akin to a Lawson's walk across the Delaunay. A walk algorithm would allow you to use geometry constraints to reduce your overall search space. To illustrate the walk concept, here is a picture taken from the Tinfour project. The walk begins at a known position and traverses the Delaunay in the direction of a goal. The result is close to the shortest number of "hops" between the two points.

While Tinfour is strictly a 2D Delaunay solution, you might find something similar in the excellent Computational Geometry Algorithms Library