This could be linked to the Packing Points into Region question. I have a rectangular grid with some positions occupied and need to place different types of points into the region with the distance constraint only applied on points of the same type.
As an example, one could consider types A, B, and C, with a minimum distance of 4, 2, and 1, respectively. This would mean that points of type A cannot be closer than 4 from each other, type B cannot be closer than 2, and so on.
There is no such restriction on points of different types which means that A and B can be placed next to each other in the grid.
My question is: Can one calculate whether it is possible to place a certain number of such points into a rectangular grid?
So far, I have read about different ways to solve the circle packing problem, and I am wondering if one could calculate the possibility before trying to place the points given a certain number of points against each type.
I am providing an example grid with some points that need to be placed.
Type = A, Required Amount = 12, Minimum Distance = 2
Type = B, Required Amount = 44, Minimum Distance = 1
Type = C, Required Amount = 9, Minimum Distance = 4
Type = D, Required Amount = 12, Minimum Distance = 1
You can solve the problem via integer linear programming with a binary decision variable $x_{ijt}$ that indicates whether unoccupied cell $(i,j)$ is assigned type $t$. Let $a_t$ denote the required amount for type $t$. The constraints are: \begin{align} \sum_t x_{ijt} &\le 1 &&\text{for all $(i,j)$} \tag1\label1\\ \sum_{i,j} x_{ijt} &= a_t &&\text{for all $t$} \tag2\label2\\ x_{i_1j_1t} + x_{i_2j_2t} &\le 1 &&\text{for $(i_1,j_1)$ and $(i_2,j_2)$ that are too close for type $t$} \tag3\label3 \end{align} Constraint \eqref{1} enforces at most one type per cell. Constraint \eqref{2} enforces the required amount for each type. Constraint \eqref{3} enforces the minimum distance requirement.
For your example data, one feasible solution is as follows: