# Covering a rectangle with arbitrary shapes of equal area, where the total area of the shapes is minimized

This is a follow up to this post, which had to be broken down since it was too long.

### 1. Definitions

Let $$A=[-2,2]^2$$, where $$\text{Area}(A)=16$$ and $$\lceil \cdot\rceil$$ is the ceiling function.

For $$\varepsilon\in\mathbb{R}$$, let $$\left\{U_i\right\}_{i=1}^{\lceil 16/\varepsilon\rceil}$$ be a sequence of pair-wise disjoint sets covering $$A$$, where for all $$i\in\mathbb{N}$$, each $$\text{Area}(U_i)$$ should equal constant $$\varepsilon$$, such that the difference between the total sum of all $$\text{Area}(U_i)$$ and $$\text{Area}(A)$$ is minimized. Furthermore, take point $$s_i\in U_i$$ where set $$\mathcal{S}=\left\{s_i:i\in\mathbb{N},1\le i\le \lceil 16/\varepsilon \rceil\right\}$$ is a sample of points.

### 2. Attempt to Convert The Definitions to Code

Below is my attempt to describe sec. 1:

Clear["Global*"]
A = Rectangle[{-2, -2}, {2, 2}]; (* Set A, i.e. [-2,2]x[-2,2] *)
U = DiscretizeRegion[A,
MaxCellMeasure -> {"Area" ->
1.8}]; (* Makes the area of all partitions "almost equal" to .1*)
S = RandomPoint /@
MeshPrimitives[U, 2];  (* A list of points from each partition *)
Show[U, Graphics[{EdgeForm[{Thick, Blue}], FaceForm[],
Rectangle[{-2, -2}, {2, 2}]}],
Graphics[{Red, Point[S]}]] (*Illustration of the code above *)


The problem is:

1. The triangles don't have equal area.
2. The only shapes I know for DiscretizeRegion are triangles. (I want arbitrary shapes, e.g. squares and rectangles, which cover $$A$$). The arbitrary shapes (i.e., $$\left\{U_i\right\}_{i=1}^{\lceil 16/\varepsilon \rceil}$$ in sec. 1.1) can "over-cover" $$A$$ as long as the total area of the shapes is minimized.

Question: How do we solve the problems 1. and 2. in sec. 2?

One possible way is using clustering:

clusters =
FindClusters[RandomPoint[Rectangle[{-2, -2}, {2, 2}], 35000], 20,
Method -> "KMeans"];

Show[{mesh = VoronoiMesh[Mean /@ clusters, {{-2, 2}, {-2, 2}}],
Graphics[{{RandomColor[], Point[#]} & /@ clusters}]}]


But areas of polygons are not the same:

area = AnnotationValue[{mesh, 2}, MeshCellMeasure]


{0.706412, 0.620505, 0.712833, 0.698375, 0.765174, 0.856666,
0.894983, 0.786204, 0.742506, 0.81401, 0.826056, 0.90378, 0.788876,
0.940046, 0.776065, 0.936281, 0.793973, 0.808283, 0.83067, 0.798302}

If you don't care about non-overlapping, you can try to scale each polygon to make the same area:

factor = Sqrt[Max[area]/area];
CanonicalizeRegion[Scale[#1, #2, #3 ]] &, {MeshPrimitives[mesh,
2], factor, AnnotationValue[{mesh, 2}, MeshCellCentroid]}];

Area /@ cover


{0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719,
0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719,
0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719}

Graphics[{Riffle[RandomColor[Length[cover]], cover] }]


But if you want squares, why not just partition into the same squares?

rec = Flatten[
Table[Rectangle[{i, j}, {i + 1, j + 1}], {i, -2, 2, 1}, {j, -2, 2,
1}]];
`
• Suppose we want to control the area of all the smaller polygons (or closed curve), so that they have a specific, equivalent area, where we take a point from each shape. How do we do this? Commented Aug 17, 2023 at 22:06
• @Arbuja RandomPoint or RegionCentroid ? Commented Aug 17, 2023 at 22:23
• Either is fine. Commented Aug 17, 2023 at 22:47
• Just apply it , RandomPoint /@ cover or RegionCentroid /@ cover Commented Aug 18, 2023 at 4:08
• or if you don't care overlapping increase # of cover like 32 and set factor : factor = Sqrt[.6/area] Commented Aug 18, 2023 at 13:55