No label defined (Q3221406)

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 3888915
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3888915

      Statements

      0 references
      0 references
      1984
      0 references
      NP-completeness
      0 references
      polynomial approximation
      0 references
      computational geometry
      0 references
      covering
      0 references
      packing
      0 references
      shifting strategy
      0 references
      quadratic algorithm
      0 references
      [For the entire collection see Zbl 0533.00025.] The study of polynomial approximation schemes seems to be one of the most difficult problems encountered in computational geometry. The authors consider two types of problems: for a finite input set of points distributed in the Euclidean space \(E_ d\) (d\(\geq 1)\) the problem is to find (i) covering, i.e. the minimum number of geometric objects (rectangles, disks, rings) needed to cover all the points; (ii) packing, i.e. the maximum number of mutually disjoint geometric objects specified by the input of points. As these problems are known to be NP-complete a new ''shifting strategy'' is developed for the design and analysis of polynomial approximation algorithms. Repetitive and nested application of the shifting strategy yields results which are the best possible in the sense of the existence of fully polynomial approximation schemes for the problems under consideration. Finally a quadratic algorithm with at most 50 \% error is given for the problem of covering with nonconvex objects (rings) in \(E_ 1\).
      0 references

      Identifiers