A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound
Let $s(N)$ denote the smallest side length of a square containing $N$ unit squares with arbitrary orientations and pairwise disjoint interiors. Nagamochi's Packing Unit Squares in a Rectangle (2005) states a rectangle packing bound from which he deduces two infinite families of exact values: $s(k^2-1) = k$ and $s(k^2-2) = k$ for every integer $k \geq 2$. We construct a family of counterexamples, local to a corner of the container, to the scoring assertion in Nagamochi's Lemma 1. These counterexamples show that the published proof of the rectangle bound is incomplete, but do not disprove the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.37410
curl -X POST /api/v1/records/arxiv/2609.37410/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.37410/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'