scientific article; zbMATH DE number 3888915

From MaRDI portal
Publication:3221406





[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\).











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 Q3221406)