# Calculate closest point without calculating hypotenuse or linear length in 2D space.

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?

-
Do you want to classify the points as A: nearer to $(0,0)$, B: nearer to $(1,1)$, or C: equidistant. Or do you want to decide which one(s) of the points is closest to $(0,0)$? Very different problems. – André Nicolas Aug 13 '12 at 23:38
@AndréNicolas: B: Nearest to (1, 1). Forget about (0, 0). – Raheel Khan Aug 13 '12 at 23:49

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.

-
Interesting answer! What happens when $b<d$ or $c<a$? – Jacob Aug 13 '12 at 23:50
Nice! Logarithms are pre-computed in my case. What about @P23's comment? If I take absolute differences for ln(Abs(b-d)) and ln(Abs(c-a)), will that A: correct a corner case, B: mess it up, C: make no difference? – Raheel Khan Aug 13 '12 at 23:55
One more thing, the pre-computed logarithms in my case are base 2 and include ln2(x1), ln2(y1) and ln2(y1) and ln2(y2) whereas your solution seems to suggest ln10(width1+/-width2) and ln10(height1+/-height2). How can I adapt this without recomputing Logarithms? – Raheel Khan Aug 13 '12 at 23:59
@RaheelKhan edited with more information. Hope this helps. – Robert Mastragostino Aug 14 '12 at 1:40
Thank you. +1 for adding the corner case. – Raheel Khan Aug 14 '12 at 1:44