scientific article; zbMATH DE number 4049041

From MaRDI portal
Publication:3785935





[For the entire collection see Zbl 0619.00022.] Recently, a growing interest in problems dealing with the movability of objects has been observed. Motion problems are manifold due to the variety of areas in which they may occur; among these areas are e.g. robotics, computer graphics, etc. One motion problem class recently being investigated is the separability problem. The separability problem is as follows: Given a set \({\mathcal P}=\{P_ 1,...,P_ M\}\) of M n-vertex polygons in the Euclidean plane, with pairwise non-intersecting interiors. The polygons are to be separated by an arbitrarily large distance through a sequence of M-1 translations while collisions with the polygons yet to be separated are to be avoided. The uni-directional separability problem arises, when all polygons are translated in a common direction; the more general problem of separability through translations in arbitrary directions is referred to as the multi-directional separability problem. Here a simple, novel approach is presented for solving an array of uni- directional and multi-directional separability problems for sets of arbitrary simple polygons. The algorithms presented here provide efficient solutions to these problems and when applied to restricted polygon classes further improvements in the time complexities are achieved.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785935)