Cut a polygon into the fewest connected pieces, each of which fits inside a unit square. This is covering if pieces can overlap, partitioning if they can't. Aamand, Abrahamsen, Browne, Goswami, Kasthurirangan, Kleist, Mitchell, Polishchuk, and Stade (arXiv:2603.23216) prove that in two dimensions, covering and partitioning give the same optimal number — a result that feels obvious until you realize it requires proof. Then they build the first polynomial-time approximation scheme (PTAS) for both problems, via local search: try replacing k pieces with k-1; if no such replacement improves the count, you're within (1 + O(1/√k)) of optimal.
The prior best was a 13-approximation, restricted to polygons without holes. The new PTAS handles holes and gets arbitrarily close to optimal.
Then they go to three dimensions. Decompose a polyhedron into pieces fitting in unit cubes. The result flips: approximating the optimal cover or partition to within a logarithmic factor is NP-hard, even for genus-zero polyhedra — simple solid shapes with no holes.
The structural transition is sharp. In 2D, local search works because local improvements are representative of global structure. The geometry of the plane ensures that replacing a small number of pieces with fewer pieces captures enough of the problem's difficulty. In 3D, the local neighborhood of any configuration is too limited — the problem's difficulty lives in global arrangements that local swaps can't access. The extra dimension doesn't just make the problem harder. It breaks the mechanism that made the 2D solution work.