0
$\begingroup$

Given $n$ number of $(x, y)$ points, I want to find out which is the closest (linear distance) to the point of origin $(1, 1)$. Both $x$ and $y$ will always be positive integers.

Due to the magnitude of numbers I am dealing with, multiplication, division, square roots are out of the question. Due to this, Pythagorean theorem is out.

Adding, subtracting or comparing $x$ and $y$ will work but I'm not sure how to achieve this.

I do not want to calculate the actual distance using Pythagorean theorem. I just want to find out which of the points are the closest to the origin. Is there a way to determine this with the restrictions above?

  • 0
    @AndréNicolas: B: Nearest to (1, 1). Forget about (0, 0).2012-08-13

1 Answers 1

2

if $a^2+b^2>c^2+d^2$

for points $(a,b),(c,d)$, then

$b^2-d^2>c^2-a^2$ $(b-d)(b+d)>(c-a)(c+a)$ $\ln(b-d)+\ln(b+d)>\ln(c-a)+\ln(c+a)$

I don't know if you're okay with taking logarithms, but this should help you compare distances to the origin if you don't want to multiply.

Check $c-a$ and $d-b$. If both are positive, $(a,b)$ is closer. If both are negative, $(c,d)$ is closer. If $c-a$ is negative and $d-b$ is positive, so both $\ln$ terms are negative, multiply the inequality by $-1$:

$(a-c)(a+c)>(d-b)(b+d)$ $\ln(a-c)+\ln(a+c)>\ln(d-b)+\ln(b+d)$

So use the absolute value signs in your computation (to save time), but note that if both of those are negative that you should interpret your answer as saying the opposite, since the inequality is flipped.

The base makes no difference, so this can be in $\log_2$. I don't know of a simple expression for $\log(a+b)$ in terms of $\log a $ and $\log b$ though.


If you want to know which of $(0,0),(1,1)$ a given point is closer to, just check if $x+y>1$

Since $x+y=1$ is the line equidistant from both points.

  • 0
    Thank you. +1 $f$or adding the corner case.2012-08-14