How can you find small denominators inside triangles? - MathOverflow

How can you find small denominators inside triangles?

2009-10-04T20:19:43Z

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 by Ilya Nikokoshev for How can you find small denominators inside triangles?

2009-10-04T22:13:37Z

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

Take the triangle's center and denote D to be its denominator.
Find all horizontal lines with y-coordinate's denominator not greater than D and that have a chance of intersecting your triangle.
Same for vertical lines.
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 by Agol for How can you find small denominators inside triangles?

2009-11-06T20:20:17Z

One way to interpret the problem is as an integer programming problem in 3-dimensions. If one has 3 points (see above) with and , then take the three lattice points .

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 http://latex.mathoverflow.net/png?%24%5Cmathbb%7BZ%7D%5E3%24) 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 of index D, where D is the determinant of the matrix , and is the volume of the parallelpiped 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 . A brute-force approach is to compute the finite abelian group , finding a basis (which will consist of at most 2 vectors since is primitive). Then translate these vectors into the fundamental domain F, and take enough positive linear combinations to generate all coset representatives of inside C. Then subtract elements from the positive semigroup , 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 is cyclic, but I'm not sure how the size of D correlates with the size of the final solution. For example, if , then the minimal vector will be with denominator . If , the minimal denominator will be by the symmetry of F.