1
$\begingroup$

Consider we have four points like this: There are 6 distinct pairs of points on this grid, but I am only interested in the pairs of points that are separated by a minimum distance. Therefore I want 4 pairs, since distance between $A,D$ and $C,B$ is $2\sqrt2$, and the remaining distances are 2.

enter image description here

Now consider this:enter image description here

The actual distances are not important but the smallest distance is a horizontal or vertical distance between two adjacent points, i.e.: $$d(A,B)=d(B,E)=d(E,F)=d(A,C) $$ etc. All the points are symmetrically put onto the grid ( figure obviously not in scale). This time the number of pairs that are at the smallest distance from each other is 24.

Last example (There are 52 such distinct pairs here).

enter image description here

Question: Given $n=2^k$ points distributed symmetrically where the horizontal and vertical distances between adjacent points are the same, is there a closed formula for finding a total number of distinct pairs of points which are at the minimum distance from each other.

Edit:

Case of 8 points is ambiguous as it takes totally different shape. For 32 points as shown in last example we take 1 by 1 squares off the outer-most edges. For $2^7=128$ we would take 2x2 such squares i.e.:

enter image description here

Then for $2^9=512$ we would take of 4x4 such square etc.

$\endgroup$
6
  • $\begingroup$ Are you imagining a formula depending only on $n$? Because arranging a square number of points (e.g., $4^2 = 16$ points) on a horizontal line gives a different number of pairs than arranging them in a square. Maybe there are upper and lower bounds in terms of $n$, but a sharp value depends on the "shape" the points are distributed into. $\endgroup$ – Eric Towers Jun 23 '20 at 20:52
  • $\begingroup$ The total number of points must be $2^k$ where k is the integer. If $k$ is even then we have squares, like the first two examples show. If it's odd we have those "near squares" like the last example show. $\endgroup$ – Scavenger23 Jun 23 '20 at 20:55
  • $\begingroup$ Have you considered a different metric? While the Euclidean metric is the most common metric, there are many others. What about the Taxicab Metric? With that, it is very easy to see minimum distances. $\endgroup$ – InterstellarProbe Jun 23 '20 at 21:02
  • $\begingroup$ It is given in the context of Euclidean distance in the equation given in my book. The context is digital modulation, and everything there is done in the context of Euclidean distance. Thanks for the hint though! $\endgroup$ – Scavenger23 Jun 23 '20 at 21:05
  • $\begingroup$ @Scavenger23 It is unclear how the points are to be distributed when $k$ is odd. Saying "symmetrically" is not specific enough. Can you describe in detail how the shape is determined? This is necessary to answer your question. $\endgroup$ – Mike Earnest Jun 23 '20 at 22:05
1
$\begingroup$

It is easiest to consider the general case, of not just a power of $2$, but of a square of $l^2$ points. We are basically counting how many horizontal and vertical lines we can draw between points. Looking only at vertical lines, we see there are $l-1$ lines for each column of $l$ points, of which there are $l$. The same argument is true for the horizontal lines. So we have $l(l-1)+l(l-1)=2l(l-1)$ lines, and therefore 'minimum distance' point pairs.

So in the particular case of even $k=2m$, we have $2^{2m}=(2^m)^2$ points, so that our formula gives $2*2^m(2^m-1)=2^{m+1}(2^m-1)$ pairs

For odd $k=2m+1$, note that there are $2^{2m+1}$ points already laid down, and $4(2^{m-2})^2$ points that would be in the corners. Then we form a square by putting the corner points back, with $2^{2m+1}+4(2^{m-2})^2=(3*2^{m-1})^2$ points. This square has, by our formula, $2*3*2^{m-1}(3*2^{m-1}-1)=9*2^{2m-1}-3*2^m$ pairs. Two things left to consider: how many of those pairs were inside our corner squares, and how many of those pairs are connecting our corner squares to 'actual' points. The corner squares have, by our formula, $2*2^{m-2}(2^{m-2}-1)=2^{2m-3}-2^{m-1}$ pairs inside each of them. And finally, for each corner square, we have one row and one column of $2^{m-2}$ connecting lines / point pairs.

So, for $k=2m+1$, we have $9*2^{2m-1}-3*2^m-4(2^{2m-3}-2^{m-1})-2*4(2^{m-2})=2^m(2^{m+2}-3)$ minimum distance point pairs!

(I have included the below as a special proof of the even case, because I liked the recursiony-ness and couldn't bring myself to delete it haha)

For the square case, i.e. even $k=2m$, $n=2^{2m}$, we have the following recursive formula, where $f(m)$ is the number of minimum distance point pairs in a square of $2^{2m}$ points:

$f(m)=2^{m+1}+4f(m-1), \quad f(1)=4$

To see this, note that the number of points is $2^{2m}=4^m$, which is a power of 4. Given the symmetry of the set up, the square of $n$ points is comprised of 4 squares of $4^{m-1}=2^{2m-2}$ points, in each quadrant of the plane. Certainly these squares have $f(m-1)$ minimum distance point pairs each, and there are 4 of them. Finally, the 4 smaller squares each have their sides made up of $2^{m-1}=\sqrt{4^{m-1}}$ points. To connect the 4 small squares to each other, we will have to connect $2^{m-1}$ points to each other 4 times (once for top left small square to bottom left, once for top left to top right, once as bottom left to bottom right, and once for top right to bottom right). So that's $4*2^{m-1}=2^{m+1}$

Then, we get from this recursive formula, the closed form:

$f(m) = \sum\limits_{i=1}^{m} 2^{m+i} = 2^{m+1}(2^m-1)$

This can be seen by expanding out $f(m)$ with the recursive formula, and keeping track of things:

$f(m)=2^{m+1}+2^2f(m-1)=2^{m+1}+2^2(2^m+2^2f(m-2))=2^{m+1}+2^{m+2}+2^4f(m-2)=\ldots=2^{m+1}+\ldots+2^{m+m-1}+2^{2(m-1)}f(1)=2^{m+1}+\ldots+2^{2m} = 2^{m+1}(2^m-1)$

(last step using geometric series formula)

$\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.