WELL-CONSTRAINED COMPLETION AND DECOMPOSITION FOR UNDER-CONSTRAINED GEOMETRIC CONSTRAINT PROBLEMS.

In this paper, we consider the optimal well-constrained completion problem, that is, for an under-constrained geometric constraint problem, add automatically new constraints in such a way that the new constraint problem G is well-constrained and the set of equations to be solved simultaneously in order to solve G has the smallest size. We propose a polynomial time algorithm which gives a partial solution to the above problem. [ABSTRACT FROM AUTHOR]