Return to Answer

added 122 characters in body

edited Apr 27, 2010 at 21:09

11
2

Doesn't the following work? UPDATE: Sorry, no it doesn't. I missed the requirement that the lattice point be on the correct side of the two lines.

Find the exact coordinates, $(u,v)$ of the intersection. These are rational numbers, and can be found by solving two linear equations. Then the nearest lattice point is $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ where $\mathrm{ROUND}$ rounds to the nearest integer.

To see that this is the closest point, translate $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ to the origin. So we need to show that, if $|u|$ and $|v|$ are $< 1/2$, then $(u,v)$ is closer to $(0,0)$ than to any other lattice point $(a,b)$. The cases of $(a,b) = (0, \pm 1)$, $(\pm 1, 0)$ or $(\pm 1, \pm 1)$ can be checked by hand. For any other $a$, $b$, one of $|u-a|$ and $|v-b|$ is greater than $1$, so the distance from $(u,v)$ to $(a,b)$ is at least $1$; which is much greater than $\sqrt{u^2+v^2} \leq \sqrt{2}/2$.

For a formal complexity analysis, the size of your input is the log of the number of digits needed to specify the two lines. All the arithmetic operations need to solve linear equations can be done in time polynomial in this logarithm.

This question is much more interesting for lattices other than the square grid. See Voronoi decomposition for details.

Doesn't the following work? Find the exact coordinates, $(u,v)$ of the intersection. These are rational numbers, and can be found by solving two linear equations. Then the nearest lattice point is $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ where $\mathrm{ROUND}$ rounds to the nearest integer.

To see that this is the closest point, translate $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ to the origin. So we need to show that, if $|u|$ and $|v|$ are $< 1/2$, then $(u,v)$ is closer to $(0,0)$ than to any other lattice point $(a,b)$. The cases of $(a,b) = (0, \pm 1)$, $(\pm 1, 0)$ or $(\pm 1, \pm 1)$ can be checked by hand. For any other $a$, $b$, one of $|u-a|$ and $|v-b|$ is greater than $1$, so the distance from $(u,v)$ to $(a,b)$ is at least $1$; which is much greater than $\sqrt{u^2+v^2} \leq \sqrt{2}/2$.

For a formal complexity analysis, the size of your input is the log of the number of digits needed to specify the two lines. All the arithmetic operations need to solve linear equations can be done in time polynomial in this logarithm.

This question is much more interesting for lattices other than the square grid. See Voronoi decomposition for details.

Doesn't the following work? UPDATE: Sorry, no it doesn't. I missed the requirement that the lattice point be on the correct side of the two lines.

Find the exact coordinates, $(u,v)$ of the intersection. These are rational numbers, and can be found by solving two linear equations. Then the nearest lattice point is $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ where $\mathrm{ROUND}$ rounds to the nearest integer.

To see that this is the closest point, translate $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ to the origin. So we need to show that, if $|u|$ and $|v|$ are $< 1/2$, then $(u,v)$ is closer to $(0,0)$ than to any other lattice point $(a,b)$. The cases of $(a,b) = (0, \pm 1)$, $(\pm 1, 0)$ or $(\pm 1, \pm 1)$ can be checked by hand. For any other $a$, $b$, one of $|u-a|$ and $|v-b|$ is greater than $1$, so the distance from $(u,v)$ to $(a,b)$ is at least $1$; which is much greater than $\sqrt{u^2+v^2} \leq \sqrt{2}/2$.

For a formal complexity analysis, the size of your input is the log of the number of digits needed to specify the two lines. All the arithmetic operations need to solve linear equations can be done in time polynomial in this logarithm.

This question is much more interesting for lattices other than the square grid. See Voronoi decomposition for details.

answered Apr 27, 2010 at 21:03

11
2

Doesn't the following work? Find the exact coordinates, $(u,v)$ of the intersection. These are rational numbers, and can be found by solving two linear equations. Then the nearest lattice point is $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ where $\mathrm{ROUND}$ rounds to the nearest integer.

To see that this is the closest point, translate $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ to the origin. So we need to show that, if $|u|$ and $|v|$ are $< 1/2$, then $(u,v)$ is closer to $(0,0)$ than to any other lattice point $(a,b)$. The cases of $(a,b) = (0, \pm 1)$, $(\pm 1, 0)$ or $(\pm 1, \pm 1)$ can be checked by hand. For any other $a$, $b$, one of $|u-a|$ and $|v-b|$ is greater than $1$, so the distance from $(u,v)$ to $(a,b)$ is at least $1$; which is much greater than $\sqrt{u^2+v^2} \leq \sqrt{2}/2$.

For a formal complexity analysis, the size of your input is the log of the number of digits needed to specify the two lines. All the arithmetic operations need to solve linear equations can be done in time polynomial in this logarithm.

This question is much more interesting for lattices other than the square grid. See Voronoi decomposition for details.