0
$\begingroup$

If I have a set A constituded by $n$ 2-dimensional points, how can I find a $\sqrt{2}$-approximation diameter of A, that is the maximum Euclidean distance between any two points in A, in linear time? Can you help me with this?

$\endgroup$
  • 1
    $\begingroup$ I bet you can compute something like this using a kd-tree. $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 15:28
  • $\begingroup$ I actually don't even know what a kd-tree is. Can you explain? $\endgroup$ – Giorgio1927 Jan 10 '18 at 17:15
  • 1
    $\begingroup$ Have you tried the internet or wikipedia :-) $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 17:30
  • $\begingroup$ I read about the kd-tree but didn't understood how to apply this to my problem... $\endgroup$ – Giorgio1927 Jan 10 '18 at 17:32
  • $\begingroup$ A kd-tree puts points into buckets. If you can find the distance of the two buckets furthest apart, you have an approximation for the furthest distance between points. $\endgroup$ – Wolfgang Bangerth Jan 10 '18 at 23:11
1
$\begingroup$

Due to admitting the $\sqrt{2}$-approximate, you could probably live with an $L^2_1$ (L1-metric in 2 dimensions) approximation of the problem, which upper bounds the Euclidean distance. Then, I would point you to an approach based on metric embedding following Bourgain’s theorem. The idea is based on transforming the problem onto a different domain using an isometric embedding, where it is much simpler to solve the problem. It is remarkable how easy one could formulate solutions to certain problems this way, such as maximum Manhattan distance between two points ($L_1$-diameter).

Let us begin by embedding the space into a space of dimension $2^d$.

Consider $x\in L^d_1$, where $d=2$ for 2D case and $\|x\|_1=\sum_i |x_i|=\sum_i sgn(x_i)\cdot x_i \geq \sum_i y_i \cdot x_i$ for all $y\in \{-1,+1\}^d$. Therefore:

$$ \|x\|_1 = max\{ \langle x,y \rangle \}. $$

It is obvious that the suggested isometric mapping is $f_y:X \rightarrow \mathbb{R}$ for each vector $y \in \{-1,1\}^2$ with $f_y(z)=\{ \langle z,y \rangle \}$. In the final map, all coordinates are concatenated together resulting in $2^d$.

We then solve the transformed problem in which every coordinate can be iteratively max-ed. See section 2.1.1 in here.

$$ \begin{align} \max_{u,v,\in S} (u-v) &= \max_{u,v,\in S} \max_{i=1}^{2^d} |u_i-v_i|\\ &= \max_{i=1}^{2^d} \text{furthest point along $\text{i}^{\text{th}}$ coordinate} \end{align} $$

As a result, the complexity is $O(2^d N)$ with constant $d$, which is linear in $N$.

Here is a simple pseudocode (thanks to umut's implementation):

d = 2;
n = 1000;
X = 10*rand(d,n);
L = zeros(d,2^d);
for i = 1:size(L,2)
    L(:,i) = bitget((i-1),d:-1:1);    
end
L(L ==0) = -1;
Y = X'*L;
diam = max(max(Y)-min(Y))

Note that you could precompute L and store for future use. For $n=1000$, this just takes 3.5ms in MATLAB whereas a naive computation would easily exceed half a second.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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