Reduction of placement problems using Minkowski decomposition

The problem of finding collision-free placements for an object amid obstacles has two well-known solutions: the task space approach and the configuration space approach. In this correspondence, we study the mathematical structure of the placement problem, and show that Minkowski decomposition of the object produces a hierarchy of intermediate reformulations. This provides the mathematical foundation for common approximate solution methods already used in applications. In particular, it provides a recipe for discretizing rotations consistently. The methods discussed are particularly effective for simple shapes.