Hello. Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it).

We're given two lines on the plane, each of them has at least two integer points (i.e. points (b,a) $(b,a)$ where b $b$ and a $a$ are in \mathbb{Z}). $\mathbb{Z}$). The lines aren't parallel, but their intersection is not necessarily in an integer point. We also are given a point (x,y) $(x,y)$ (also integer) that doesn't belong to both lines.

The problem is to find a point (x',y') $(x',y')$ in the same quarter as $(x,y)$ (as separated by the lines) closest to intersection of the lines. It may be $(x,y)$ itself, but not further than (x,y). most likely it's closer.

The (x,y) $(x,y)$ point is seemingly needed just to make the problem NP-complete instead of NP-hard. The problem is claimed to have a polynomial solution, but I doubt that it really persists. Could anyone solve it or provide a proof that it's NP-complete?

Hello. Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it).

We're given two lines, each of them has at least two integer points (i.e. points (b,a) where b and a are in \cal{Z}). mathbb{Z}). The lines aren't parallel, but their intersection is not necessarily in an integer point. We also are given a point (x,y) (also integer) that doesn't belong to both lines.

The problem is to find a point (x',y') in the same quarter (as separated by the lines) closest to intersection of the lines, but not further than (x,y). The (x,y) point is seemingly needed just to make the problem NP-complete instead of NP-hard.

The problem is claimed to have a polynomial solution, but I doubt that it really persists. Could anyone solve it or provide a proof that it's NP-complete?

Hello. Here's a question that originates from StackOverflow (and the SO crowd isn't really qualified to solve it).

We're given two lines, each of them has at least two integer points (i.e. points (b,a) where b and a are in \cal{Z}). The lines aren't parallel, but their intersection is not necessarily in an integer point. We also are given a point (x,y) (also integer) that doesn't belong to both lines.

The problem is to find a point (x',y') in the same quarter (as separated by the lines) closest to intersection of the lines, but not further than (x,y). The (x,y) point is seemingly needed just to make the problem NP-complete instead of NP-hard.

The problem is claimed to have a polynomial solution, but I doubt that it really persists. Could anyone solve it or provide a proof that it's NP-complete?