Revisions to How to find a closest integer point to the intersection of two lines?

image fixed (inlining HTTP images doesn't work anymore); for more info, see https://gist.github.com/Glorfindel83/9d954d34385d2ac2597bbe864466259f

Source Link

edited Dec 30, 2018 at 18:16

Glorfindel

2.8k
6
30
39

alt text http://robbymckilliam.github.com/pictures/linemo.png

just fixing dead figure links. Should be permanent links now!

Source Link

edited Jun 15, 2011 at 11:18

Robby McKilliam

1k
8
14

alt text http://www.itee.uq.edu.au/%7Erobertm/pictures/linemo.png alt text http://robbymckilliam.github.com/pictures/linemo.png

added 1 characters in body; added 11 characters in body; Post Made Community Wiki

Source Link

edited Apr 29, 2010 at 9:53

Robby McKilliam

1k
8
14

Let $A(x)$ denote the angle between $\ell$ and $x$. Our motivation is now very similar to that in Diophantine approximation. That is, find all of the best approximationapproximations for $A(x)$, our problem is solved by the best approximation that first yields $A(x) \leq \theta$. It so happens that $A(x)$ is a very similar function to $F(p,q)$. To give this some context I will say that $F(p,q)$ is, in a sense, computing an inner product between two vectors, whereas $A(x)$ is computing an angle. In this context it is not surprising that the algorithms for Diophantine approximation can be used.

The OP (particularly on stack overflow, but also here) seems to have thrown quite a number of red herrings into the problem statement (rather annoying). For example, knowledge of the point (x,y) does nothing other than tell you which quadrant you are looking in. The statement about it converting the problem to NP-complete rather than NP-hard doesn't make any sense. Also, the fact that the lines pass through integer points isappears to be irrelevant.

Let $A(x)$ denote the angle between $\ell$ and $x$. Our motivation is now very similar to that in Diophantine approximation. That is, find all of the best approximation for $A(x)$, our problem is solved by the best approximation that first yields $A(x) \leq \theta$. It so happens that $A(x)$ is a very similar function to $F(p,q)$. To give this some context I will say that $F(p,q)$ is, in a sense, computing an inner product between two vectors, whereas $A(x)$ is computing an angle. In this context it is not surprising that the algorithms for Diophantine approximation can be used.

The OP (particularly on stack overflow, but also here) seems to have thrown quite a number of red herrings into the problem statement (rather annoying). For example, knowledge of the point (x,y) does nothing other than tell you which quadrant you are looking in. The statement about it converting the problem to NP-complete rather than NP-hard doesn't make any sense. Also, the fact that the lines pass through integer points is irrelevant.

Let $A(x)$ denote the angle between $\ell$ and $x$. Our motivation is now very similar to that in Diophantine approximation. That is, find all of the best approximations for $A(x)$, our problem is solved by the best approximation that first yields $A(x) \leq \theta$. It so happens that $A(x)$ is a very similar function to $F(p,q)$. To give this some context I will say that $F(p,q)$ is, in a sense, computing an inner product between two vectors, whereas $A(x)$ is computing an angle. In this context it is not surprising that the algorithms for Diophantine approximation can be used.

The OP (particularly on stack overflow, but also here) seems to have thrown quite a number of red herrings into the problem statement (rather annoying). For example, knowledge of the point (x,y) does nothing other than tell you which quadrant you are looking in. The statement about it converting the problem to NP-complete rather than NP-hard doesn't make any sense. Also, the fact that the lines pass through integer points appears to be irrelevant.