¿Cómo puede encontrar denominadores pequeños dentro de triángulos?

Question

Darsh preguntó sobre en el 20 Seminario de preguntas:

Tomar un triángulo en R ^ 2 con coordenadas en los puntos racionales. ¿Podemos encontrar el punto denominador más pequeño en el interior? (Considerar denominador de un elemento de Q ^ 2 que la lcm de los denominadores de las coordenadas.) (Sugerencia: puede hacer la versión de 1-d usando fracciones continuadas.)

Answer 1

Una forma de interpretar el problema es como un entero de un problema de programación en 3-dimensiones. Si uno tiene 3 puntos de $(a_i/c_i,b_i/c_i) \in \mathbb{R}^2, i=1,2,3$ con $gcd(a_i, b_i, c_i) =1$$c_i \geq 1$, luego tomar los tres celosía puntos de $P_i=(a_i, b_i, c_i) \in \mathbb{Z}^3$.

Tome el cono de C se extendió por entero positivo combinaciones de $P_i$ (este es el proyectiva región sentado encima del triángulo). Entonces uno quiere encontrar la celosía punto de $\mathbb{Z}^3$ dentro del interior de este cono con menor z de coordenadas. Esto puede ser interpretado como un problema de programación lineal entera. Sin embargo, no sé lo suficiente acerca de la programación entera para saber si esto va a ayudar (Bufanda parece haber pensado precisamente este problema, pero no la dirección de la complejidad computacional). La siguiente proporciona un enfoque posible, pero no podría ser mejor que Nikokoshev del enfoque excepto en ciertos regímenes.

Estos vectores generar un sublattice $\Lambda \subset \mathbb{Z}^3$ de índice D, donde D es el determinante de la matriz $[P_1,P_2,P_3]$, y es el volumen del paralelepípedo de F generado por estos vectores. Uno puede ver que un entramado de vectores en este cono con un mínimo de z-coordinar debe estar en esta F, puesto que F es fundamental el dominio de la acción de $\Lambda\cap C$. Un ataque de fuerza bruta enfoque es calcular el finito grupo abelian $\mathbb{Z}^3/\Lambda$, la búsqueda de una base (que consistirá en la mayoría de los 2 vectores desde $P_i$ es primitivo). A continuación, traducir estos vectores fundamental en el dominio de F, y tomar suficiente lineal positiva combinaciones para generar todos los coset representantes de $\mathbb{Z}^3/\Lambda$ dentro de C. Luego restar elementos de la positiva semigroup $\Lambda\cap C$, hasta encontrar todos los coset representantes en el dominio de F, y encontrar uno con un mínimo de z de coordenadas. Este enfoque debe ser bastante eficaz cuando D es pequeño o el grupo $\mathbb{Z}^3/\Lambda$ es cíclica, pero no estoy seguro de cómo el tamaño de D se correlaciona con el tamaño de la solución final. Por ejemplo, si $D=1$, el mínimo vector de se $P_1+P_2+P_3$ con denominador $c_1+c_2+c_3$. Si $D\geq 2$, el mínimo denominador se $<(c_1+c_2+c_3)/2$ por la simetría de F.

Answer 2

He aquí un ejemplo de algoritmo que encuentra el más pequeño denominador punto en el interior:

1. Tomar el triángulo del centro y denotan D ser su denominador.
2. Encuentra todas las líneas horizontales con coordenada y del denominador no mayor que D y que tienen una probabilidad de la intersección de su triángulo.
3. Mismo para las líneas verticales.
4. Se cruzan estas líneas de familias, seleccione los puntos en el interior de su triángulo y minimizar su denominador.

Esto hace ver como un insatisfactorio algoritmo, pero entonces el problema podría beneficiarse de ser expresado en una forma diferente, quizás

• Podemos encontrar el más pequeño denominador punto en el interior el uso de algunos hermosos O(D) algoritmo?

(donde, presumiblemente, D es la respuesta final)