Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given n number of (x, y) points, I want to find out which is 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 closest to the origin. Is there a way to determine this with the restrictions above?

share|improve this question
1  
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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