Packing-constrained point coverings

MaRDI QIDQ4906867zbMATH OpenFDO

Authors Veit Elser

Publication date 28 February 2013

Full work available at URL https://arxiv.org/abs/1101.3468

zbMATH Keywords

configurations of points in the planepacking-constrained point covering problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other designs, configurations (05B30) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: In the packing-constrained point covering problem, PC^2, one seeks configurations of points in the plane that cannot all be covered by a packing arrangement of unit disks. We consider in particular the problem of finding the minimum number of points N for which such a configuration exists and obtain the bounds 11 <= N <= 55. The disparity of these bounds is symptomatic, we believe, of the fact that PC^2 belongs in a higher complexity class than the standard packing and covering problems.

Recommendations

• Motif patterns and coverings of points with unit disks. I
• scientific article; zbMATH DE number 1182895
• Valid constraints for the Point Packing in a Square problem

Cited in

(7)

• Motif patterns and coverings of points with unit disks. I
• Valid constraints for the Point Packing in a Square problem
• Packing points into a unit cube in higher space
• Primitive point packing
• Covering and packing of rectilinear subdivision
• Simultaneous packing and covering in the Euclidean plane
• SIMULTANEOUS PACKING AND COVERING IN THREE–DIMENSIONAL EUCLIDEAN SPACE

This page was built for publication: Packing-constrained point coverings

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