Skip to main content
image fixed (inlining HTTP images doesn't work anymore); for more info, see https://gist.github.com/Glorfindel83/9d954d34385d2ac2597bbe864466259f
Source Link
Glorfindel
  • 2.8k
  • 6
  • 30
  • 39
added 1 characters in body; added 11 characters in body; Post Made Community Wiki
Source Link

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.

added 1 characters in body
Source Link
Loading
added 3 characters in body
Source Link
Loading
added 113 characters in body
Source Link
Loading
added 18 characters in body
Source Link
Loading
deleted 18 characters in body; added 9 characters in body; edited body; deleted 7 characters in body
Source Link
Loading
fixed picture; added 2 characters in body; added 2 characters in body
Source Link
Loading
Source Link
Loading