Covering points by congruent rectangles

Definitions and mathematical statement

Let $S\subset\mathbb R^2$ be a finite point set and let $R$ be a prescribed nondegenerate rectangle with positive side lengths. In the rotated-copy interpretation indicated by the research summary, an allowed placement is $g(R)$, where $g(x)=Qx+b$, $b\in\mathbb R^2$, and $Q$ is a planar rotation. Reflection does not enlarge the set of placements of a rectangle. The copies have the same side lengths as $R$; they are not rescaled. Define \[ \operatorname{OPT}(S,R)=\min\left\{m\in\mathbb Z_{\ge0}:\exists g_1,\ldots,g_m, \ S\subseteq\bigcup_{i=1}^m g_i(R)\right\}. \] Under the usual covering convention copies may overlap and boundary points are covered. For $S=\varnothing$ the optimum is $0$; approximation ratios are evaluated on nonempty $S$.

Construct efficient approximation algorithms for this minimum-cardinality covering problem, and determine the best achievable approximation ratio. For example, in a polynomial-time formulation a guarantee $\rho\ge1$ requires that every admissible nonempty input $(S,R)$ be covered by an algorithm's output of $m_A(S,R)$ congruent copies satisfying \[ m_A(S,R)\le\rho\,\operatorname{OPT}(S,R). \] If the optimal guarantee depends on input size or rectangle aspect ratio, that dependence must be specified instead of assuming a universal constant. An optimality theorem also needs a computational model and any complexity assumptions for lower bounds.

The source does not specify whether the rectangle is fixed once for all inputs or supplied as part of each input, the coordinate and placement representation, or the deterministic versus randomized and constant-factor versus size-dependent approximation conventions. The statement alone does not state the allowed motions; rotations are included here on the evidence of the supplied research summary. These choices require confirmation for a uniquely specified approximation threshold.

The registry labels the exact best ratio open/unverified. It reports bounded approximations for special cases involving axis-parallel squares or rectangles and NP-hardness for closely related covering variants; these reports do not supply an approximation threshold or hardness theorem for the unrestricted rotated-copy problem. The source index's open label was not checked item by item against later literature.

Short English statement

Cover a finite planar point set with as few congruent placements of a given rectangle as possible. Find efficient approximation algorithms and the best guaranteed ratio when rotations are allowed, with the missing computational and approximation conventions recorded for review.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $3900004$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attribution: David Eppstein and cited proposers.
• David Eppstein, The Geometry Junkyard: Open Problems, "Covering points by congruent rectangles": https://ics.uci.edu/~eppstein/junkyard/open.html. HTML extraction accessed 2026-07-29. Item-level later resolution was not checked.
• The supplied research summary mentions special-case approximation results and hardness for related problems, but provides no original-paper citations or precise theorems.