0

Let's consider a 2d array A with A(i,j)=0 whatever i and j initially. Let's now add n points for which A(i,j)=1, i.e., sum(sum(A))=n

The question is:

What is the optimal spatial distribution of these n points that would minimize the average Euclidean distance map of 0 to 1.

with Matlab that would be:

A=zeros(10,10) % a grid of 10 by 10, only 0s
A(1:2)=1;
A(2,3)=1; 
A(4,3)=1; 
A(5,5)=1; %a guess: assign n=4 pixels to 1 

dmap = bwdist(A) % Calculate Euclidean distance map (shortest distance from 0 to 1)
dmap(dmap==0)=[]; % Remove 0 distance (e.g., from A(5,5) to A(5,5))
average_min_distance_from_0_to_1 = mean(dmap)

So I want to find the optimal point distribution (i.e., this line A(1:2)=1; A(2,3)=1; A(4,3)=1; A(5,5)=1) so that average_min_distance_from_0_to_1 is the minimum among all the possible permutations.

I think it may be a variation of the geometric median problem (The point that minimizes the sum of euclidean distances to a set of n points), but in my case I try to find the optimal distribution of more than 1 point.

Thanks for any help. Best.

Hadi
  • 1,203
  • 1
  • 10
  • 20
Doby
  • 1
  • your problem has not a unique answer and it is an optimization problem, consider using genetic algorithm in matlab (which seems the best option in case of your problem) – Hadi Aug 29 '21 at 14:28
  • Hello Hadi. Thanks for your answer. Genetic algorithm was indeed the good choice. I did not know about it and found a simple explanation of the method there: https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3. It was enough to build a simple algorithm that solved my problem. Thanks for the indication. – Doby Aug 31 '21 at 16:08

0 Answers0