¿Cómo encontrar el punto entero más cercano a la intersección de dos rectas?

Question

Aquí hay un pregunta que se origina en StackOverflow .

Dadas son dos líneas en un plano, especificadas por ecuaciones ( $a x + b y = c$ ) con coeficientes enteros. Las líneas no son paralelas y no pasan necesariamente por ningún punto entero. Dado también es un punto entero $(x,y)$ (x e y están en $\mathbb{Z}$ ) que no se encuentra en ninguna de las dos líneas.

El problema es encontrar el punto entero $(x',y')$ más cercana a la intersección de las líneas que se encuentran en el mismo cuadrante del plano que $(x,y)$ . Puede ser $(x,y)$ pero nos interesa el caso no trivial de que exista un punto aún más cercano.

Aparte de ser una forma de especificar el cuarto de interés, el punto (x,y) es aparentemente necesario para asegurar que el problema es NP o más fácil. Sin este punto, parece que la respuesta podría no ser polinómica con respecto a los parámetros de la línea $a_1$ , $a_2$ , $b_1$ etc.

Se afirma que el problema tiene una solución polinómica, pero dudo que exista realmente. ¿Existe una solución o una prueba de su completitud NP?

Answer 1

Si el punto $(x,y)$ está en un cuadrante obtuso entre las líneas el problema se resuelve fácilmente enumerando los puntos de la red en una esfera cerrada de radio $\sqrt{2}$ sobre el punto de intersección por lo que sólo consideraré el caso de que $(x,y)$ se encuentra en un cuadrante agudo.

El problema se puede convertir en uno muy parecido a la aproximación diofantina inhomogénea. Conozco al menos un algoritmo que encontrará definitivamente la respuesta correcta en $O\left(\tfrac{1}{\theta}\right)$ operaciones en las que $2\theta$ es el ángulo agudo entre las líneas. El algoritmo es una pequeña modificación del que se da en la página 19 de La tesis de Vaughan Clarkson . Estoy muy seguro de que el algoritmo de Cassels (o una pequeña modificación del mismo) resolverá el problema en $O\left(1 + \log\tfrac{1}{\theta}\right)$ operaciones (página 34 de 1 ), pero no sé muy bien cómo mostrarlo, o qué modificación hay que hacer. Antes de describirlo, hay que saber un poco sobre la aproximación diofantina no homogénea.

Dejemos que $\alpha$ y $\beta$ sean números reales. Definir la función

$F(p,q) = |\alpha p - q - \beta|$ .

El problema de aproximación diofántica no homogénea consiste en minimizar $F(p,q)$ sobre números enteros $p$ y $q$ donde $q$ es positivo. El par $(p, q)$ se llama mejor aproximación si $F(p,q) < F(p',q')$ para todos $q' < q$ . Las mejores aproximaciones describen los mínimos encontrados como $q$ y la magnitud de $p$ aumento. Hay varios algoritmos que pueden enumerar todas las mejores aproximaciones. Dos ejemplos son el "algoritmo ingenuo" (página 19 de 1 ) y el algoritmo de Cassel (página 34 de 1 ). El problema del PO no es exactamente el mismo que éste, pero es tan parecido que los algoritmos (al menos el algoritmo ingenuo) se repiten.

Dejemos que nuestras dos líneas sean $\ell_1$ y $\ell_2$ y que $2\theta < \pi/2$ sea el ángulo entre ellos. Será más fácil describir la aproximación si fijamos la intersección de estas líneas en el origen y buscamos el punto más cercano en la red trasladada $\mathbb{Z}^2 + t$ donde $t$ es la traducción adecuada. Definir $\ell$ para ser la única línea que pasa por el origen y biseca el ángulo agudo entre $\ell_1$ y $\ell_2$ . El ángulo entre $\ell$ y $\ell_1$ y $\ell$ y $\ell_2$ es $\theta$ . El problema se puede plantear ahora como:

Encuentra el punto $x \in \mathbb{Z}^2 + > t$ que está más cerca del origen tal que el ángulo entre $x$ y $\ell$ es menor o igual que $\theta$

Dejemos que $A(x)$ denotan el ángulo entre $\ell$ y $x$ . Nuestra motivación es ahora muy similar a la de la aproximación diofantina. Es decir, encontrar todas las mejores aproximaciones para $A(x)$ nuestro problema se resuelve con la mejor aproximación que primero da $A(x) \leq \theta$ . Sucede que $A(x)$ es una función muy similar a $F(p,q)$ . Para dar un poco de contexto diré que $F(p,q)$ es, en cierto sentido, computar un producto interior entre dos vectores, mientras que $A(x)$ está calculando un ángulo . En este contexto no es de extrañar que se puedan utilizar los algoritmos de aproximación diofantina.

Sólo consideraré el "algoritmo ingenuo" y me limitaré a dar una visión geométrica de su funcionalidad, esto debería ser suficiente para convencer a la mayoría. Trabajar esto rigurosamente está realmente más allá de una respuesta escrita en MO, pero toda la maquinaria requerida está en 1 . El "algoritmo ingenuo" enumera cada punto de $\mathbb{Z}^2 + t$ que es un punto de la red más cercano a cualquier punto de la línea $\ell$ . En otras palabras, localiza consecutivamente (empezando por el origen) cada punto de la red en $\mathbb{Z}^2 + t$ cuya célula de Voronoi (en este caso los cuadrados) intersecan $\ell$ . Una imagen podría ser útil

No es difícil idear un algoritmo que lo haga, basta con empezar en el origen y comprobar dónde $\ell$ siguiente cruza un límite de una célula de Voronoi. También es fácil ver que los puntos que localiza son un superconjunto de las mejores aproximaciones para $A(x)$ . El primer punto que el algoritmo encuentra tal que $A(x) < \theta$ es la solución del problema (el círculo azul).

Este algoritmo se llama "ingenuo" porque comprueba muchos puntos de la red que no son las mejores aproximaciones. El algoritmo de Cassels lo mejora sustancialmente para la función $F(p,q)$ . Es probable que una mejora similar sea posible para $A(x)$ y alguien podría querer solucionarlo.

El OP (particularmente en stack overflow, pero también aquí) parece haber arrojado un buen número de pistas falsas en el planteamiento del problema (bastante molesto). Por ejemplo, el conocimiento del punto (x,y) no hace otra cosa que decirte en qué cuadrante estás mirando. La afirmación de que convierte el problema en NP-completo en lugar de NP-duro no tiene ningún sentido. Además, el hecho de que las líneas pasen por puntos enteros parece ser irrelevante.

Answer 2

No creo que el problema sea NP-completo, porque estás trabajando en una dimensión fija. Como la mayoría de nosotros creemos que el caso más difícil es cuando el ángulo entre las dos líneas es muy pequeño, entonces se puede tomar la línea L a mitad de camino entre las dos líneas, y proyectar ortogonalmente sobre ella para la función objetivo. Entonces tenemos un problema de programación entera en 2 dimensiones -- las dos desigualdades especifican el lado propio de las dos líneas. Hendrik Lenstra en "Integer Programming with a fixed number of variables" en Mathematics of Operations Research, demostró que cuando la dimensión es fija hay un algoritmo de tiempo polinomial para la PI (usando una variante de la reducción de la base de la red L^3). También está el artículo http://www.math.uni-klu.ac.at/or/doctoralschool/deloera.pdf "Integer Polynomial Optimization in Fixed Dimension" que menciona que una función objetivo polinómica convexa también tiene un algoritmo de tiempo polinómico en dimensión fija, por lo que debería servir para este problema.

[Comentarios añadidos] Utilizando los dos documentos que mencioné en mis comentarios http://mpi-inf.mpg.de/~soeren/pubs/2ip.ps http://homepages.cwi.nl/~aardal/journal_rev.ps se puede proceder de la siguiente manera: Vamos a tener líneas de apoyo superior e inferior ortogonales a la línea de punto medio L. Estas siempre tendrán la propiedad de que sabemos que hay al menos un punto de red en el cuadrilátero limitado por las líneas originales y la línea de apoyo (aunque al principio haya degenerado en un triángulo). Al principio, la línea de apoyo inferior es la que pasa por la intersección de las dos líneas originales. La línea de apoyo superior se puede calcular observando que cualquier disco de radio > sqrt(2)/2 debe contener un punto de la red, por lo que se puede encontrar la distancia más pequeña a lo largo de la línea media en la que se puede situar el centro de dicho disco -- será donde la línea de centro ortogonal a cada una de las líneas originales tenga la distancia sqrt(2)/2. Por simple trigonometría se puede ver que si el número de bits en el número original es N, entonces necesitamos como máximo 2N bits para especificar este punto (es decir, si los denominadores son alrededor de n para los originales, entonces los denominadores para los puntos anteriores son como máximo n^2). Ahora usa el algoritmo del primer artículo que te dice en tiempo lineal en el número de bits del problema si hay o no puntos de la red en el cuadrilátero. Haz una búsqueda binaria mirando una línea de prueba a mitad de camino entre las líneas de apoyo, y prueba cada uno de los dos cuadriláteros. Después de sólo unos N pasos (recuerde que N es el logaritmo de los coeficientes) llegará a un cuadrilátero con un área y una anchura pequeñas. En ese punto puedes enumerar rápidamente todos los puntos de la red en él y probarlos para el mínimo. Este algoritmo probablemente se ejecuta en tiempo O(N^2) donde N es el número de bits en los coeficientes originales.

[otra adición para simplificar las cosas]:

La idea para resolver el problema es hacer lo siguiente:

1) Encuentre una aproximación suficientemente buena a la distancia mínima, y el punto de la red que la alcanza, de modo que pueda encerrar esa región en un rectángulo cuyos lados sean paralelos a la $x$ y $y$ ejes, con un área suficientemente pequeña, $A$ y el perímetro $P$ . Es fácil ver que se pueden enumerar todos los puntos de la red dentro de dicho rectángulo en el tiempo $A+P$ y luego comprueba cuáles son los que te dan el mínimo. [Cambiando la notación] Dejemos que $n$ sea el número de bits para especificar el problema y $N=2^n$ . Sea el ángulo entre las dos líneas denotado por $2 \theta$ y la línea media por $L$ .

2) Como he mencionado, cualquier disco con radio $> \sqrt{2}/2$ debe contener un punto de red. Para ello, colocamos un disco de este tipo entre las dos líneas, y lo más cerca posible del punto de intersección. Vemos que la distancia desde el punto de intersección hasta el centro del disco que acaba de encajar, es $\sqrt{2}/2 \csc \theta$ . Si $\theta \ge \pi/6$ (digamos) podemos encerrar todo el triángulo delimitado por las líneas y la línea tangente al disco ortogonal a $L$ en un rectángulo de tamaño y perímetro constantes, así que simplemente probamos todos esos puntos. Tenga en cuenta que en cualquier caso $\theta \ge c/N$ para alguna constante absoluta $c$ desde cuando $\theta$ es lo suficientemente pequeño $\cos \theta \approx 1 - \theta^2/2$ y $\cos 2 \theta$ viene dado por un producto punto entre los coeficientes de las rectas y por tanto tiene como máximo $2n$ bits.

3) En caso contrario, llamamos al algoritmo descrito en http://mpi-inf.mpg.de/~soeren/pubs/2ip.ps sólo una vez, siendo la función objetivo el producto punto entre $(x,y)$ y un vector paralelo a $L$ y las cuatro restricciones: entre las dos líneas, y el producto punto con $L$ es $\ge 0$ y $\le$ el límite que obtenemos al colocar el disco. Porque $\theta$ es lo suficientemente pequeño y acotado lejos de 0, ahora podemos dibujar un rectángulo que encierre el punto producido por el algoritmo cuya área y perímetro estén acotados, independientemente del número de bits, que debe contener la respuesta, y volvemos a enumerar todos los puntos de ese rectángulo.

Answer 3

Puedes intentar aplicar el algoritmo del artículo

B. N. Delone, "Un algoritmo para las "celdas divididas" de una red", Izv. Akad. Nauk SSSR Ser. Mat., 11:6 (1947), 505-538

Answer 4

Dejemos que $n$ sea el tamaño de la entrada, es decir, el número de dígitos de la entrada en alguna base, o la suma o el máximo de los logaritmos de las magnitudes de los números de la entrada-- todos ellos son equivalentes a efectos de big-O.

Estrategia: aplicar como máximo $O(n)$ (transformaciones lineales que preservan el área dejando un eje de coordenadas fijo) a obtener un problema fácil, resolver el problema fácil, y luego aplicar la secuencia inversa de cizallas para obtener la solución de nuevo en el espacio de coordenadas original. en el espacio de coordenadas original.

PROBLEMA FÁCIL #1: cuando al menos uno de los dos rayos delimitadores está alineado con el eje.

PROBLEMA FÁCIL #2: cuando las dos direcciones de los rayos delimitadores apuntan a los interiores de diferentes cuadrantes del plano.

Se omiten los detalles de los problemas fáciles, ya que son sencillos y no son la parte interesante o desafiante de este problema.

Supongamos que tenemos un caso no fácil del problema: es decir, ambas direcciones de los rayos delimitadores apuntan al interior del mismo cuadrante; con el fin de que ambas apunten al primer cuadrante.

Elija uno de los dos rayos delimitadores y llámelo "primario" y el otro "secundario". Si el rayo primario tiene pendiente $< 1$ , intercambia los ejes de coordenadas, de modo que la semirrecta primaria tenga pendiente $\ge 1$ .

Dejemos que $a/b \ge 1$ sea la pendiente del rayo delimitador primario, con $a \ge b \gt 0$ tomado directamente de las ecuaciones de entrada. Sea $q,r$ sea el cociente y el resto de la división de $a$ por $b$ . Es decir, $q=\mathrm{floor}(a/b), r=a-q b, a \ge b \gt r \ge 0$ .

Aplicar a la geometría del problema el cizallamiento que deja la $y$ eje fijo y toma $(1,q)$ à $(1,0)$ ; en otras palabras, la transformación lineal que deja $(0,1)$ fija y toma $(1,0)$ à $(1,-q)$ . Mantenga la designación "primario" en la imagen del rayo delimitador primario. Esta transformación de cizalladura disminuye la pendiente del rayo primario a r/b, manteniendo su dirección en el primer cuadrante (si $r>0$ ), o en paralelo a la $x$ eje (si $r=0$ ).

Obsérvese que la solución antes de esta transformación de cizalla puede describirse mediante cualquiera de las siguientes caracterizaciones equivalentes (equivalentes porque ambos dirs de rayos delimitadores apuntan al primer cuadrante):

• (a) "el punto entero del trimestre más cercano al punto de intersección" (por definición)
• (b) "el punto entero del trimestre con el mínimo $x+y$ ",
• (c) "el punto entero del trimestre con el mínimo $x$ entre todos los puntos con un mínimo de $y$ ".
• (d) "el punto entero del trimestre con el mínimo $y$ entre todos los puntos con un mínimo de $x$ "

Hay tres casos.

Caso 1: Tras el cizallamiento, ambos rayos siguen apuntando al interior del primer cuadrante.

En este caso, la solución del problema cizallado es, de nuevo, las siguientes caracterizaciones equivalentes:

• (a') "el punto entero del cuarto transformado más cercano al punto de intersección transformado"
• (b') "el punto entero del cuarto transformado con el mínimo $x+y$ "
• (c') "el punto entero del cuarto transformado con el mínimo $x$ entre todos los puntos con un mínimo de $y$ ".
• (d') "el punto entero del cuarto transformado con el mínimo $y$ entre todos los puntos con un mínimo de $x$ "

Centrándonos en (d) y (d') queda claro que la solución del problema transformado es la solución transformada del problema original.

En el problema transformado, el rayo delimitador primario tiene pendiente $r/b$ con $b > r > 0$ (todavía en el caso 1 aquí) por lo que su pendiente es $< 1$ ; Por lo tanto, al comenzar el análisis del problema transformado como antes, intercambiaremos las coordenadas para que su pendiente $b/r > 1$ . Observe que lo que hemos hecho hasta ahora es realizar una iteración del algoritmo euclidiano es decir, $a$ ha sido sustituido por $b$ y $b$ ha sido sustituido por el resto de $a$ dividido por $b$ .

Repetir tantas veces como nos encontremos en el caso 1 (manteniendo la designación "primaria" en el mismo de los dos rayos aunque se transformen). Dado que el $a,b$ siguen los valores euclidianos comenzando con dos de los números de entrada originales, el conocido análisis del algoritmo euclidiano nos dice que el caso 1 puede ocurrir como máximo $O(n)$ veces: es decir, si llegamos hasta el final del algoritmo euclidiano, $b$ se convertirá en 0, lo que nos sacará del caso 1 (si es que no lo hemos dejado ya antes).

Caso 2: La cizalla hace que el rayo delimitador primario sea horizontal, y el rayo secundario cizallado sigue apuntando al primer cuadrante.

Exactamente igual que en el caso 1, (a')=(b')=(c')=(d') y, por tanto, la solución del problema transformado es la transformación de la solución del problema original. Además, el problema transformado es ahora un caso del PROBLEMA FÁCIL Nº 1; resuelva eso, transforme inversamente la solución de vuelta al espacio original; hecho. (Cuando esto se encuentra recursivamente desde el caso 1, significa que hemos llegado hasta el final del algoritmo euclidiano).

Caso 3: La cizalla lleva la dirección del rayo delimitador secundario fuera del interior del primer cuadrante, hacia el $x$ eje o el cuarto cuadrante. (Esto es independiente de si la dirección del rayo delimitador primario se convirtió en horizontal o se mantuvo en el primer cuadrante).

Este caso es relativamente fácil de resolver, pero tenemos que tener cuidado en este caso la transformada del punto dentro del cuarto más cercano a la intersección (es decir, que satisface (a)) es no necesariamente el punto del cuarto transformado más cercano a la intersección transformada (es decir, que satisface (a')). Sin embargo es cierto que la transformada del punto que satisface (d) es el punto que satisface (d'). Por tanto, el problema de la transformada, aunque fácil, es no en la forma del problema original. En cambio, es un caso de:

PROBLEMA FÁCIL #3: Las direcciones de los rayos delimitadores apuntan ambas al semiplano +x, pero hacen no ambos apuntan al interior del mismo cuadrante, y se nos pide que encontremos el punto que satisface (d) en lugar de (a) (que son no necesariamente el mismo en este caso).

Así que he descrito un algoritmo para transformar el problema original en uno de los tres problemas fáciles, en $O(n)$ iteraciones.

Análisis de la complejidad

El número de iteraciones es $O(n)$ por lo que el tiempo total de ejecución es $O(n)$ veces el coste por iteración.

¿Cuánto cuesta una iteración? Cada iteración consiste en un pequeño número constante de operaciones aritméticas, cada una de las cuales es como máximo $O(M(\mathrm{num\ digits\ in\ operands}))$ donde $M$ significa el coste de una multiplicación (véase el artículo de la wikipedia " Coste computacional de las operaciones matemáticas "). Pero, ¿cuántos dígitos son?

Pues bien, a primera vista parece que los valores intermedios y finales podrían tener hasta $n^2$ dígitos, lo que haría que el tiempo total de ejecución $O(n M(n^2)))$ . Además, se puede sospechar que el $n$ -El punto testigo de un dígito podría ayudar a disminuir este límite. Pero el siguiente análisis más detallado revela que no es tan malo, y que el $n$ -El testigo de un dígito en realidad no hace ninguna diferencia.

Cada transformación es una cizalla seguida de un cambio de eje de coordenadas: $$\begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 \\ - q_i & 1 \\ \end{pmatrix} = \begin{pmatrix} - q_i & 1 \\ 1 & 0 \\ \end{pmatrix}$$ donde $q_0, q_1, ...$ es la secuencia de cocientes $q$ que se produce en el algoritmo euclidiano (posiblemente cortado por el caso 3). Así que la norma matricial de la matriz acumulativa es $\leq$ el producto de la $q_i$ 's, que es como máximo el valor original de $a$ que tiene $n$ dígitos. Y lo mismo puede decirse de la matriz inversa acumulativa. Eso nos dice que el número máximo de dígitos que aparecen en la respuesta o en cualquier valor intermedio es $O(n)$ . Por lo tanto, el tiempo de ejecución total es $O(n M(n))$ .

Por cierto, la secuencia de cálculos de matrices enteras de 2x2 que se sigue es en realidad bien conocida como el EEA (Algoritmo Euclidiano Extendido) para el CRT (Teorema Chino del Resto). Si se lleva hasta el final la matriz acumulativa representa una transformación lineal invertible con coeficientes enteros que lleva la dirección del rayo primario original a un eje de coordenadas que puede ser un bloque de construcción útil para muchas aplicaciones (en particular, los problemas del Proyecto Euler :-) ). Así que uno podría pensar que podríamos simplemente usar una implementación preempacada de AEE como bloque de construcción; pero no veo cómo hacer que eso funcione para este problema, debido a la posibilidad de tener que parar antes de tiempo debido al caso 3.

Answer 5

¿No funciona lo siguiente? ACTUALIZACIÓN: Lo siento, no lo hace. Se me pasó el requisito de que el punto de la red esté en el lado correcto de las dos líneas.

Encuentra las coordenadas exactas, $(u,v)$ de la intersección. Estos son números racionales, y se pueden encontrar resolviendo dos ecuaciones lineales. Entonces el punto de la red más cercano es $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ donde $\mathrm{ROUND}$ redondea al número entero más cercano.

Para ver que este es el punto más cercano, traduce $(\mathrm{ROUND}(u), \mathrm{ROUND}(v))$ al origen. Así que tenemos que demostrar que, si $|u|$ y $|v|$ son $< 1/2$ entonces $(u,v)$ está más cerca de $(0,0)$ que a cualquier otro punto de la red $(a,b)$ . Los casos de $(a,b) = (0, \pm 1)$ , $(\pm 1, 0)$ o $(\pm 1, \pm 1)$ se puede comprobar a mano. Para cualquier otro $a$ , $b$ Uno de los $|u-a|$ y $|v-b|$ es mayor que $1$ por lo que la distancia de $(u,v)$ à $(a,b)$ es al menos $1$ que es mucho mayor que $\sqrt{u^2+v^2} \leq \sqrt{2}/2$ .

Para un análisis de complejidad formal, el tamaño de su entrada es el logaritmo del número de dígitos necesarios para especificar las dos líneas. Todas las operaciones aritméticas necesarias para resolver las ecuaciones lineales pueden realizarse en un tiempo polinómico en este logaritmo.

Esta cuestión es mucho más interesante para retículas distintas a la cuadrada. Véase Descomposición de Voronoi para más detalles.