0
$\begingroup$

I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find its name or further information on it. So any help to find an efficient algorithm for its solution or a pointer to the name of the problem at hand would be very helpful.

Given $ n \times m $ matrix $ M $ of integers from $ [0, w) $ and a set $ P $ of $ w $ points (i.e. tuples of indices in the matrix),
find a permutation $ M' $ of the values of $ M $, such that the global distance function $ f(M') = $ $ \sum_{i=0}^{n-1}{ \sum_{j=0}^{m-1} } { \left(i - x\left(P[M'[i, j]]\right)\right)^2 + \left(j - y\left(P[M'[i, j]]\right)\right)^2 } $ is minimal.

Explained in a different way, consider an image with $ n \times m $ pixels, where each pixel is of one of $ w $ distinct colors. We then want to rearrange the pixels such that all pixels of the same colors from a group around the seed point of the same color. We are allowed the swap the colors of pixels as long as the total number of pixels for each colors stays constant. Below you find an example of the resulting image from a random initial image with a hundred equally likely color as starting point located around randomly pixed seed points. The result was obtained by iteratively picking two points at random and swapping them if the global distance function after swapping is reduced. Doing this for millions of times approaches (at least a local) optimum depicted in the images. However this approach is rather slow for larger values of $ n $ and $ m $. So I am looking for a faster solution to obtain the result. Also a non-discrete solution where polygons would describe the final areas would be appreciated. I was also considering Voronoi tesselations (which can be computed much faster), however they do not work in my case due to the fixed area constraint (i.e. the colored sections should be of equal size in this example).

Area preserving distance optimization

$\endgroup$
4
  • $\begingroup$ I don't understand what $P$ is. Can you specify it more clearly? You say it is a set of $w$ points; what is a point? What is the meaning of the notation $P[\cdot]$ when $P$ is a set? What are $x,y$? Those are used without being defined. $\endgroup$ – D.W. Dec 31 '20 at 23:32
  • $\begingroup$ I don't have time to investigate this, but I feel like the polygon boundaries in your problem are parallel to the Voronoi boundaries. This suggests a more continuous solution involving moving the boundaries along their normals, which you could probably optimise with a gradient descent method (e.g. the Levenberg-Marquardt algorithm). $\endgroup$ – Pseudonym Jan 1 at 9:21
  • $\begingroup$ @D.W. $ P $ is just a set of seed points to which I want to minimize the distance of each areas, very similar to the seed points in, e.g., voronoi tesselations. $\endgroup$ – raisyn Jan 1 at 14:21
  • $\begingroup$ @Pseudonym Thank you very much, that is indeed an interesting observation, I will take a closer look! $\endgroup$ – raisyn Jan 1 at 14:22
0
$\begingroup$

This appears to be an instance of the assignment problem, where you are trying to match up the $nm$ cells of $M$ with the $nm$ cells of $M'$. For each place where $M[i,j]$ may get permuted to, you can compute the cost of that: namely, if it is permuted to $M'[i',j']$, then its cost is $(i'-x P[M[i,j]])^2 + (j' - y P[M[i,j]])^2$. Then you can use standard algorithms for the assignment problem, such as the Hungarian algorithm. Whether this is practical or not may depend on how large $nm$ is. If it's not practical, you could instead try a heuristic, such as local search algorithm based on making swaps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.