3
$\begingroup$

I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space that fulfils all distance constraints.

I wish to generate arrangements of the points where all constraints are fulfilled. Any approach is allowed as long as each arrangement is independently generated from the others.

What algorithm is most suitable? Mainly in terms of efficiency.

As an extension, how would I incorporate constraints on the angle defined by three points? And on the dihedral angle defined by four points (the dihedral angle between points ABCD is the angle between the plane defined by ABC and the plane defined by BCD)?

$\endgroup$
2
$\begingroup$

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool. Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane. You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each pair of points $v,w$ with distance bounds $[\ell,u]$, we create an edge $v \to w$ with length $(\ell+u)/2$. However, this does have some limitations: typical graph layout algorithms try to get the distances between vertices correct, but also try to avoid edges that cross each other; whereas in your case you don't care about crossings. So, your problem might be easier.

Another possibility is to apply the ideas used for graph layout to your problem. There are several algorithmic techniques for graph layout. For instance, you could use a spring-based model, where you have a spring between each pair of vertices that have a distance bound, and the spring tries to keep those pair of vertices a suitable distance apart.

A third approach is to use black-box mathematical optimization. Introduce an objective function $\Phi$ which, given a set of locations for the points, calculates a penalty value (how "badly" the arrangement violates your constraints), and then try to find an arrangement that minimizes $\Phi$.

For instance, suppose for each pair $v,w$ of points, you have a lower bound $\ell_{v,w}$ and an upper bound $u_{v,w}$. You could define

$$\Phi(x_1,\dots,x_n) = \sum_{i,j} \frac{[||x_i - x_j||_2 - (u_{i,j} + \ell_{i,j})/2]^2}{(u_{i,j} - \ell_{i,j})^2},$$

and then use some optimization technique to find an arrangement $x_1,\dots,x_n$ that minimizes $\Phi(x_1,\dots,x_n)$. For instance, you could try using hillclimbing, gradient descent, or other convex optimization methods. This approach might be sensitive to the initial values for $x_1,\dots,x_n$, so you might want to repeat it multiple times with different random choices for the initial value, and take the best result.

Finally, you could try using simulated annealing.


The latter two approaches can be easily adjusted to incorporate angle constraints, simply by modifying the objective function appropriately to add a term that penalizes angles that differ from the desired value.

$\endgroup$

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.