Packing problems where parts of objects are allowed to intersect

Question

I'm interested in packing problems where the objects are allowed to intersect.

For a simple example, consider stacking 1×2 tiles on a nxn chessboard. Each 1×2 tiles consists of part X and Y (both 1×1). X is not allowed to intersect with any other tiles, but Y can intersect with other Ys. What is the maximum number of tiles that can be fitted into the chessboard?

Example2: Fitting infinitely long radial strips in a disk of radius n. X is 1x1 region at the head of the strip. All X must lie in the disk,and cannot intersect with other tiles. Instead of 1x1, Y is now 1x.. (extends to infinity), and can stick out of the disk, or intersect with other Ys. What's the maximum number of such strips that can be fitted into the disk?

For the general question, what about planar (or in higher dimensions) packing geometric objects U in region V with some additional…

1. "constraints" (some parts of U needs to be kept at some distance from parts of U, parts of U must be connected to the boundary of V, etc.) or

2. "relaxations" (parts of U can stick out of V, U is allowed to be distorted, etc.)?

3. What about the asymptotic bounds on the relationship (numbers, sizes) of such U and V?

Any reference to relevant literature would be appreciated, since I found none.

Answer 1

Sometimes you will be able to relate this to a usual packing problem. For the initial example with a region $X$ and a complementary region $Y$, let $Z$ be the set of points which are closer to $X$ than to the boundary of the tile.

Then the region $Z$ on one tile cannot intersect the region $Z$ on another tile: Let $P$ be an intersection point, $d_1$ the distance to region $X$ of the first tile, $e_1$ the distance to the boundary of the first tile, and similarly $d_2,e_2$: Then we have $d_1 < e_1$ and $d_2 < e_2$ so we either have $d_1 < e_2$ or $d_2 < e_1$ but in the first case a disc of radius between $d_1$ and $e_2$ around the intersection point is contained in the second tile but intersects region $X$ of the first tile, contradiction, and a similar contradiction in the second case.

So the number of tiles we can pack for this problem is at most the number of regions of shape $Z$ we can pack in the usual way.

In your case where $X$ is a $1\times 1$ subtile of a $1 \times 2$ tile, this is sharp: The region $Z$ is a pentagon made from a $1\times 1$ tile and a quarter of a $1\times 1$ tile. We can pack at most the area of the space divided by the area of this pentagon into the space, and this is sharp to within $O(n)$, since we can make the pentagons completely fill space by packing four $1\times 2$ tiles into a cross so that the regions $Y$ overlap and then tiling the plane with this cross. For an $n\times n$ grid there is some unused space near the edges but only $O(n)$.