How can you find small denominators inside triangles?

Question

Darsh asked over at the 20 questions seminar:

Take a triangle in R^2 with coordinates at rational points. Can we find the smallest denominator point in the interior? (Consider denominator of an element of Q^2 to be the lcm of the denominators of the coordinates.) (Hint: you can do the 1-d version using continued fractions.)

Answer 1

Here's an example algorithm that finds the smallest denominator point in the interior:

1. Take the triangle's center and denote D to be its denominator.
2. Find all horizontal lines with y-coordinate's denominator not greater than D and that have a chance of intersecting your triangle.
3. Same for vertical lines.
4. Intersect these line families, select points inside your triangle and minimize their denominator.

This does look like an unsatisfying algorithm, but then your problem might benefit from being phrased in a different way, perhaps

• Can we find the smallest denominator point in the interior using some beautiful O(D) algorithm?

(where, presumably, D is the final answer)

Answer 2

One way to interpret the problem is as an integer programming problem in 3-dimensions. If one has 3 points $(a_i/c_i,b_i/c_i) \in \mathbb{R}^2, i=1,2,3$ with $gcd(a_i, b_i, c_i) =1$ and $c_i \geq 1$, then take the three lattice points $P_i=(a_i, b_i, c_i) \in \mathbb{Z}^3$.

Take the cone C spanned by positive integer combinations of $P_i$ (this is the projective region sitting above the triangle). Then one wants to find the lattice point of $\mathbb{Z}^3$ inside the interior of this cone with smallest z-coordinate. This may be interpreted as an integer linear programming problem. However, I don't know enough about integer programming to know if this will help (Scarf seems to have thought about precisely this problem, but doesn't address the computational complexity). The following gives one possible approach, but might not be any better than Nikokoshev's approach except in certain regimes.

These vectors generate a sublattice $\Lambda \subset \mathbb{Z}^3$ of index D, where D is the determinant of the matrix $[P_1,P_2,P_3]$, and is the volume of the parallelepiped F spanned by these vectors. One can see that a lattice vector in this cone with minimal z-coordinate must lie in this F, since F is a fundamental domain for the action of $\Lambda\cap C$. A brute-force approach is to compute the finite abelian group $\mathbb{Z}^3/\Lambda$, finding a basis (which will consist of at most 2 vectors since $P_i$ is primitive). Then translate these vectors into the fundamental domain F, and take enough positive linear combinations to generate all coset representatives of $\mathbb{Z}^3/\Lambda$ inside C. Then subtract elements from the positive semigroup $\Lambda\cap C$, until you find all coset representatives in the fundamental domain F, and find the one with minimal z-coordinate. This approach should be pretty effective when D is small or the group $\mathbb{Z}^3/\Lambda$ is cyclic, but I'm not sure how the size of D correlates with the size of the final solution. For example, if $D=1$, then the minimal vector will be $P_1+P_2+P_3$ with denominator $c_1+c_2+c_3$. If $D\geq 2$, the minimal denominator will be $<(c_1+c_2+c_3)/2$ by the symmetry of F.