Simplex with smallest possible total edge length in set of points

user_17893156 0
Viewed 65

My question is similar to this one, however there are a few key differences

Given a set X of points in d dimensions and a query point q, my goal is to find the simplex span by d+1 points in X that

  • has q as an interior point
  • has no other point of X as an interior point
  • has the smallest possible total edge length

The last condition may be altered, f.e. the smallest possible circumcircle would be fine as well.

How could I find this simplex in reasonable time? Delaunay does not yield satisfying results, as the generated simplices satisfy a global optimality condition and not my local one.

A brute force solution is possible, however I'm interested in a more elegant solution. I thought about a graph-based approach, but did not find a good solution yet. A proposal for a solution as well as links to some papers or even just keywords are warmly welcome, as I'm not that keen in Graph Theory. Preprocessing the points is possible.

computational-geometry graph-theory optimization
1 Answers

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

A 2D Lawson's Walk

user_126646680
Related