I was wondering whether it is equivalent to minimizing the radius of a circle containing the needed number of pixels (or square grid nodes), but it seems that already for 5 pixels they diverge (yielding a "+" shape VS a "b" shape).

One possible question to ask is - if these packings are incremental: can we always add one pixel to a smaller optimal packing to obtain an optimal packing?

Other possible questions are - for which infinite sets of numbers of pixels do the problem of minimizing distance sum and the problem of minimizing containing circle radius yield the same packing(s), and when are these unique (possibly modulo rotation and reflection)

Spinning off the last questions, do packings inside radius of n*sqrt(2) satisfy those?

I also wondered whether incremental addition of new pixels to the previous optimal cluster would continue giving optimal results. Intuitively it seems possible but I haven't been able to prove that conclusively. (I am still using an incremental addition approach)

Calculating all interpixel distances is computationally quite expensive. Your suggestion is much faster. I now increment by minimizing the mean radial distance to the previous cluster.

Both approaches create a 'd' at 5 pixels but diverge at 6 pixels (min. interpixel distance gives a 2x3 rectangle, whilst min. radial distance gives a '+' with an infilled corner).

The metric for compaction must be lightweight (e.g. mean radial distance) but the process of finding the optimal solution doesn't have to be (because I will store them in a look up table). A 'brute force' option might be to treat pixels as square particles with a mass and a gravitional attraction, then randomly scatter them and see how they coalesce (perhaps repeating the process a few times to check that the true optimal solution is found)

For the variant in which one wishes to minimise the sum of the pairwise L1 distances, see this paper:

http://www.sciencedirect.com/science/article/pii/S0925772110000726

I do not have a free access to sciencedirect, but I like the thought of considering L1 distance instead of L2. Check it out: the sum of Manhattan distances between, e.g., (x1,y1), (x2,y2), (x3,y3) is exactly 2dx+2dy, where dx=max{x1,x2,x3}-min{x1,x2,x3} and dy=max{y1,y2,y3}-min{y1,y2,y3}. The problems are, however, not equivalent, since, e.g., three points in a row give optimal sum of Manhattan distances (4), while the sum of their Euclidian distances is also 4, while the optimum is 2+sqrt(2).

Let's see if we any nice rule holds for more points. For 4 of them, let's sort x-coordinates and y-coordinates separately (the horizontal distances and vertical distances are independent, so even if xj will no longer correspond to yj, the result would not change) in the ascending order. Then dx=x4-x1 and dy=y4-y1. The total sum of L1 distances will then be 3dx+(x3-x2)+3dy+(y3-y2).

For 5 points, with similar notations, the total L1 distance sum is 4dx+2(x4-x2)+4dy+2(y4-y2). However, I do not imagine an O(n^7.5) algorithm mentioned in the abstract. Yet, looking at the target sum being so closely related to dx (horizontal distance between the maximum and the minimum), dy (vertical equivalent), and the axial distances between the second maximum and the second minumum, etc., I feel that at least for n^2, the unique solution MUST be a square.

After some thinking I suppose that for n^2 points in a square, L1 distance sum should be

2n^2 * T_{n-1} = (n-1)n^3(n+1)/3

Thanks Adam, this looks like it could be very helpful for constraining up to n=80...

I wil read it carefully

Also available here:

http://arxiv.org/abs/1009.5628

I looked at the paper. So at least for L1 distances, we do not have uniqueness, the incremental approach partially fails (some optimal solutions do not extend to +1 optimal solutions, while some optimal solutions are not extension of -1 optimal solutions), and 4x4 square would yield L1 sum of 320, while the optimal result of 318 is displayed in the paper. Good luck.

Thank you Artiom you have been very helpful! (I have only just seen your previous post now, I must have posted mine at the same time!).. I will keep working on this problem