1
$\begingroup$

I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points and sort them. Instead of using distances $\sqrt{x^2+y^2}$, can I use $|x|+|y|$ as my key? Also, I would like to find out the complexity for both approaches.

$\endgroup$
3
$\begingroup$

The two notions of distance are not equivalent. That is, you can find a pair of points $p,q$ such that $p$ is closer to the origin with respect to the distance $\sqrt{x^2+y^2}$ (known as $L_2$), and $q$ with respect to the distance $|x|+|y|$ (known as $L_1$). An example is $p=(2,2)$ and $q=(3,0)$. However, you can simplify your task by considering $x^2+y^2$ instead of $\sqrt{x^2+y^2}$.

There is no need to sort the distances. Instead, you can use a comparison-based linear time selection algorithm.

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