# Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$

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.

## 1 Answer

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.