We consider the fine-grained complexity of covering a set of n points 𝒫 in the Euclidean plane using a fixed set of geometric objects corresponding to rigid-body translations and, where permitted, rotations of a specified shape Υ. Under the Exponential Time Hypothesis (ETH), and both with and without a pairwise disjointness constraint, we establish that no 2^o (√n) -time algorithm can exist for this problem in the following cases: (case 1) translatable unit disks; (case 2) translatable fixed-area axis-aligned squares; or (case 3) translatable and rotatable fixed-area equilateral triangles. Furthermore, by way of establishing the #P-completeness under parsimonious reductions of positive 1-in-3-SAT with a cubic planar 3-connected clause-variable incidence graph - pertinent to hardness reductions for counting tilings (Moore Discrete Comput. Geom. 26 (4) ; 2001), (Pak J. Comb. Theory. Ser. A 120 (7) ; 2013) - we establish in each case that there exists a quadratic time reduction from #SAT to counting the possible coverage-induced partitions of 𝒫. Finally, we consider constraints on the density of the points in 𝒫 that make our coverage problems tractable. In particular, letting Υ be any (not necessarily connected) subregion of a radius 1/2 disk characterized by a semi-algebraic function, and letting 𝒫 be a set of n points, we consider the density requirements that: (constraint 1) every 3 points have a minimum bounding disk of radius greater than 1; or (constraint 2) any 5 points have a minimum bounding disk of radius at least 2. Here, when Υ is part of the input, under both (constraint 1) and (constraint 2), and with and without a pairwise disjointness requirement, we show that finding a minimum cardinality set of translatable and/or rotatable instances of Υ covering all points in 𝒫 is fixed-parameter tractable in the size of the semi-algebraic description of Υ.
Barish et al. (Thu,) studied this question.