A Solution of Polygon Containment, Spatial Planning, and Other Related Problems Using
Minkowski Operations · 1990
This paper gives a complete solution to the polygon containment problem under translation and other related problems for all kinds of two dimensional regions. The solution is achieved in three steps. First, it is shown that the containment and the related problems can be directly mapped to Minkowski decomposition and addition problems. Minkowski decomposition, which is intrinsically a geometric problem, is then reformulated in terms of set operations and set theoretic tools are used to reduce the computational complexity of the problem. Finally, a new technique, termed as decomposition boundary tracing technique, is devised and employed for the solution of the decomposition problem. This new technique brings out a unfied algorithmic approach to solve all kinds of decomposition problems in a two dimensional space,