¿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

Este problema es un poco oscuro, pero hay varias soluciones eficientes que pueden interesarte. Yo empezaría por tratar de encontrar primero una copia del artículo de Lee y Chang, a menos que domines el francés, en cuyo caso la tesis de Guigue contiene una exposición actualizada.

Mehta, S., M. Mukherjee, y G. Nagy. "Constrained integer approximation to 2-D line intersections". Second Canadian Conf. on Computational Geometry. 1990.

Lee, H. S., y R. C. Chang. "Aproximación de vértices de un polígono convexo con puntos de cuadrícula en el polígono". Algorithms and Computation. Springer Berlin Heidelberg, 1992. 269-278.

Guigue, Philippe. Construcciones geométricas con precisión fija. Diss. Universidad de Niza Sophia-Antipolis, 2003.