The constraint condition for motion of objects in contact must be derived and analyzed for the sensing, control and planning of it. Assuming that a polyhedron moves in contact with another polyhedron and that no friction exists between them, the condition can be represented by homogeneous linear inequalities. In this paper, the inequalities is analyzed from the viewpoint of the complexity of the algorithm for solving it.
Applying the singular value decomposition to the coefficient matrix of the inequalities and introducing an intersecting hyperplane, it is shown that the problem is equivalent to finding the intersection of half spaces or the convex hull of a set of points. The singular value decomposition enables us to find the solution in the minimal dimensional space, where the complexity of the algorithm is also minimal. A new algorithm is also proposed which is not optimal as asymptotic complexity, but significantly fast in the practical cases and independent of the dimension of the space. The algorithm is applied to the departure motion planning, and it is also shown that the basis of nonnegative linear combination, which is the solution of the inequalities, become the minimal number of direction for the searching.