Aproximación diofántica - Punto de la red más cercano a una línea (2d)

Question

Considere una línea 2D $A x + B y + C = 0$ con coeficientes enteros $A, B, C$ . Encuentra el punto de la red $(x, y)$ más cercano a la línea, tal que $|x|, |y| \leq n$ para algún número entero $n$ . ( $x$ y $y$ son números enteros, por supuesto).

Se da la circunstancia de que la línea cruza la $y$ eje en $y_0 = -\frac{C}{B}$ y $-1 < y_0 < 0$ . Es decir, la línea se desplaza del origen, pero no por "mucho". Nótese que si la línea pasara por el origen, es decir $y_0 = 0$ , $(x,y)$ podrían enumerarse fácilmente con convergentes y semiconvergentes de $\frac{A}{B}$ . Sin embargo, aquí tenemos una pequeña compensación, por lo que ya no es el caso. Sospecho que todavía existe algún enfoque similar.

¿Cuál sería una forma eficiente de conseguir ese $(x,y)$ ¿punto?

Por ejemplo, la siguiente imagen muestra alguna de estas líneas (en rojo) y el punto más cercano a ella (en azul) para $n = 8$ .

Answer 1

Bien, me imaginé esto. Como sospechaba un enfoque similar al algoritmo euclidiano funciona. La idea es la siguiente:

Para cualquier $x$ , $y = [\frac{A x + C}{-B}]$ où $[z]$ significa $round(z)$ . Así que esto pide esencialmente encontrar un $x$ en $[x_{min}, x_{max}]$ que minimiza $d(x)=|A x + C + B\ [\frac{A x + C}{-B}]|$ .

Vamos a tratar primero un par de casos extremos. Si $A=0$ entonces $d(x)$ no depende de $x$ por lo que sólo podemos devolver $x_{min}$ . Por lo tanto, a partir de ahora podemos asumir $A\neq0$ .

Si $A<0$ podemos simplemente negar ambos $A$ y $C$ que hace que $A>0$ sin cambiar el valor de $d(x)$ . Por lo tanto, a partir de ahora podemos asumir $A>0$ .

En primer lugar, hay que tener en cuenta que $|z|=|-z|$ y $-[z] = [-z]$ . Es decir, el signo no afecta al functor de valor absoluto, y puede moverse libremente por el functor de redondeo.

La afirmación anterior se deduce entonces trivialmente porque: $$ \begin{align} d(x) & =|A x + C + B\ [\frac{A x + C}{-B}]| \\\\ & =|-A x - C - B\ [\frac{A x + C}{-B}]| \\\\ & =|-A x - C + B\ [\frac{-A x - C}{-B}]| \end{align} $$

Del mismo modo, podemos cambiar el signo de $B$ para que sea siempre positivo. Lo conseguimos: $$ \begin{align} d(x) & =|A x + C + B\ [\frac{A x + C}{-B}]| \\\\ & =|A x + C - B\ [\frac{A x + C}{B}]| \end{align} $$

Lo que es conveniente ahora es que ambos $A>0$ y $B>0$ . Escribamos $A=qB+r$ donde $0 \leq r < B$ . Entonces: $$ \begin{align} d(x) & =|A x + C - B\ [\frac{A x + C}{B}]| \\\\ & =|(qB+r) x + C - B\ [\frac{(qB+r) x + C}{B}]| \\\\ & =|(qB+r) x + C - B\ [qx+\frac{r x + C}{B}]| \\\\ & =|(qB+r) x + C -Bqx -B\ [\frac{r x + C}{B}]| \\\\ & =|r x + C -B\ [\frac{r x + C}{B}]| \\\\ \end{align} $$ Esto significa que podemos hacer $A<B$ simplemente sustituyéndolo por el resto de la división de $A$ por $B$ . Por lo tanto, a partir de ahora se asume $A<B$ .

Desde $A<B$ esto significa que el rango $[y_{min},y_{max}]$ de valores que $y=[\frac{A x + C}{B}]$ toma es menor que $[x_{min}, x_{max}]$ y esta es la observación crucial aquí.

Al principio dijimos que para cualquier $x$ , lo mejor $y=[\frac{A x + C}{-B}]$ . Recíprocamente para cualquier $y$ , lo mejor $x=[\frac{B y + C}{-A}]$ .

Esto da $d(x) = B y + C + A [\frac{B y + C}{-A}]$ que es el mismo problema pero con límites reducidos. En particular $(A, B, C) \implies (B, A\%B, C)$ como en el algoritmo euclidiano, y el tamaño del rango para $y$ es $\frac{A\%B}{B}$ de la de rango para $x$ .

Esto da una $O(\log B)$ algoritmo de búsqueda $(x,y)$ . Sólo hay que tener un poco de cuidado en cubrir correctamente los límites de los rangos $[x_{min},x_{max}]$ y $[y_{min},y_{max}]$ .

Aquí está mi aplicación .