Packing-constrained point coverings

zbMATH Open1263.52011arXiv1101.3468MaRDI QIDQ4906867FDOQ4906867

Authors: Veit Elser 

Publication date: 28 February 2013

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.

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

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

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)

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)