Detecting geometric infeasibility

摘要

The problem of deciding whether one or more objects can be removed from a set of other planar or spatial objects arises in assembly planning, computer-aided design, robotics and pharmaceutical drug design. In this context, it will be shown that certain D-dimensional arrangements of hyperplanes can be analyzed in the following way: only a single connected component is traversed, and the arrangement is analyzed as an arrangement of surface patches rather than full hyperplanes. In special cases, this reduction allows for polynomial time bounds, even if the boundary of the set of reachable placements has exponential complexity. The described techniques provide the basis for an exact method for translational assembly planning with many degrees of freedom. Experiments obtained with an implementation suggest that problems with random planning methods, which are related to the choice of internal parameters can be avoided with this exact method. In addition, unsolvability can be established and the program can be applied to the verification of symbolic rules describing the geometry.