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
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
0.8717785477638245
0 references
0.8484563231468201
0 references
0.8104714751243591
0 references
0.799913763999939
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