No label defined (Q3785935)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4049041
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4049041

      Statements

      0 references
      0 references
      1987
      0 references
      computational geometry
      0 references
      separability problem
      0 references
      time complexities
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references