PhD Thesis

Distance Bound Smoothing under Orientation Constraints

Work default illustration


  • Started: 15/02/2013
  • Thesis project read: 29/09/2014


In the context of distance formulations for solving position problems, some branch-and-prune methods have been proposed, but the lack of a tight constraint propagation in the prune operations hinders their efficiency. However, the distance bound smoothing techniques, mainly developed in structural biology, produce tight bounds for problems formulated using distances. Moreover, distance formulations are inherently ambiguous: the same set of distances typically represent different configurations. This is due to the orientation constraints of the problems which are discarded when using only distance constraints. The orientation ambiguities make the number of solutions to grow exponentially with the size of the problem. The undesired solution can be filtered out in a post-process step, but it would be better if the solving process could directly focus on the valid solutions.
The relevance of orientations becomes obvious when translating different sets of geometric
constraints into distance constraints. For example, when translating angle constraints into distance constraints, orientation constraints are also generated.

The main objective of the PhD thesis is to develop distance bound smoothing techniques,
able to incorporate orientation constraints, in order to improve the prune step in existing branch-and-prune methods.