# Find the farthest points in d-dimensional space

We have $n$ points with $d$ coordinates each and we want to find two of them for which distance between them is the biggest, in Manhattan metric.

The obvious algorithm has complexity $O(n^2 \cdot d)$ (for each pair of points we check the difference between them in $\Theta(d)$ time). What I'm interested in is an algorithm with complexity $O(n \cdot 2^d)$.

You can share any other algorithm, though. I'll be glad to learn anything.

Edit: I've come up with the algorithm. It's in my comment, below.

-
Isn't typically $d = \Theta(\log n)$? So instead of $O(n^2 \log n)$ you are asking for $O(n^2)$? –  gt6989b Aug 27 '13 at 14:10
It seems so. But I wanted to be more specific. I think complexity with $d$ is more helpful than without it. –  user39042 Aug 27 '13 at 14:15

Find the corners of the smallest hyperrectangle which bounds your points. This can be done in $O(n\cdot d)$ time (by computing the maximum and minimum values in each dimension). Note that there are $2^d$ corners in a $d-$dimensional hyperrrectangle.

Next, find a point in your data set which closest (using the Manhattan metric) to each of your $2^d$ corners and lies on a face of your hyperrectangle (done in $O(n\cdot 2^d \cdot d)$ time).

Find the farthest points (using the Manhattan metric) amongst these $2^d$ points (done in $O(2^{2d}\cdot d)$ time.

The time complexity for this algorithm is $O(n \cdot d + n\cdot 2^d \cdot d+ 2^{2d} \cdot d ) = O(n\cdot2^d \cdot d)$ if $n \ge 2^d$.

-

If you are willing to change the notion of distance by replacing the Euclidean distance by the sup-norm (namely, the maximum of the coordinate differences $|x_i-y_i|$) then there is an algorithm that's linear in $n$. For each coordinate, find the least and greatest value of the coordinate (this can obviously be done in linear time). Repeat this for each coordinate and then pick the biggest difference. This should be of complexity $O(n\cdot d)$.

-
I forgot to add than it's Manhattan metric (the one you wanted)... Sorry. I don't know how your algorithm would work, though. Let's take this example: ideone.com/47IZVd. Mins are $[6, 6, 3, 2, 1, 6, 1, 15]$ and maxs are $[96, 74, 91, 98, 99, 83, 98, 86]$. The biggest difference is $99-1=98$ but it's only on one coordinate and the expected answer is 398. –  user39042 Aug 27 '13 at 18:21

I've come up with an optimal algorithm on my own! This is the most difficult task I've solved in my life, so focus.

So. First I'll explain the example for $d=2$ and then generalize it. We want to find the farthest points in 2D. Let's determine for each point it's distance from $(0;0)$. It's $|x_i|+|y_i|$. When we have two points we can calculate the distance between them using their distance from $(0;0)$. So for $(1;2)$ and $(6;7)$ we have 3 and 13 so distance between them is 10. BUT for points $(1;7)$ and $(6;-1)$ it doesn't work. Why? Because with the first pair we have segment which looks like / while in the second one the segment looks like \ . In the first case it's ok, because the distance between first point and $(0;0)$ and between second point and $(0;0)$ shares the beginning of the distance and in the second case not necessarily. How can we fix that? By rotating the coordinate system or, more specifically, the axis X, negating all $x_i$. Then for $(1;7)$ and $(6;-1)$ we have respectively $7-1=6$ and $-1-6=-7$ so the distance between them is $6+|-7|=13$ and that's correct. Knowing that, we can find $min$ and $max$ of $y_i+x_i$ and $min2$ and $max2$ of $y_i-x_i$ in linear time. What can we do with it? Check $|min-max|$ and $|min2-max2|$ and the bigger one will be our result (biggest distance between two points in 2D).

Now we can generalize this for $d>2$. Firstly, we don't find only $y_i+x_i$ and $y_i-x_i$ but sums with all combinations of signs. For example for: 1 2 3 4, we have to check sums: $1+2+3+4$, $1+2+3-4$, $1+2-3+4$, $1+2-3-4$, $1-2+3+4$, $1-2+3-4$, $1-2-3+4$ and $1-2-3-4$. Why not $-1+2+3+4$? Because it's just negation of $1-2-3-4$ (just different sign). So we keep all max's and min's for all such combinations of signs. There will be $2^{d-1}$ max's and $2^{d-1}$ min's. After reading the points we just find maximum from $|max_i-min_i|$ for $i \in \left<0;2^{d-1}\right>$ (assuming we count from 0). It's worth adding that we go through the combinations with binary code. So 0000, 0001, 0010, 0011, etc. If there's 0 on a position we negate the number. The complexity is $O(n \cdot d \cdot 2^d)$, because for each point we check all $2^{d-1}$ combinations and for each of them we calculate the sum in $\Theta(d)$ time. That's not the complexity I wanted, though! Let's go deeper. Here's the code for the algorithm above: https://ideone.com/smc9dL with $d \le 16$ (wb = abs in my language).

We can notice that we don't have to calculate the sum every time. We can first calculate the sum and then subtract or add a certain value if only one position was changed. Thus, instead of binary code we can use Gray code where only one position changes. But how to move from one "Gray number" to another? We can use the formula: $\text{Gray}(x) = x \oplus \lfloor\frac{x}{2}\rfloor$ which calculates $x$-th Gray number. But how to get position on which the value changes? We can first calculate $\text{Gray}(x) \oplus \text{Gray}(x-1)$ (which will be a power of 2 - zeroes with only one 1 - ...0001000...) and in $O(d)$ time check it's position. But it will have the same complexity as in the previous algorithm! Yes, it will. But we can notice, that these positions can be calculated once. Therefore, we calculate for each number in range $\left<1;2^{d-1}\right)$ in $O(d)$ time. And later we check them in constant time. We also have to remember whether bit 0 switched to 1 or 1 to 0. In the first case we add and in the second we subtract. The final algorithm is here: https://ideone.com/Lhvbac .

Why were you interested in a $O(n\cdot 2^d)$ algorithm? –  Jacob Aug 28 '13 at 22:38
Because $n >> d$. That's a problem from SPOJ and with $d \le n$ the task wouldn't make much sense and now it's pretty interesting. –  user39042 Aug 30 '13 at 0:51