title: Reduction of placement problems using Minkowski decomposition.
abstract: 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.
authors.affiliation: Informatics Inst., Univ. of Amsterdam, Netherlands.
authors.forename: L
authors.initials: L
authors.lastname: Dorst
authors.forename: N
authors.initials: N
authors.lastname: Ahmed