Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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)

share|improve this answer
1  
When I originally asked this question (in the seminar mentioned in the posted question), I did ask for an efficient algorithm, but I probably didn't emphasize it enough. :-) Solving the 1D version by continued fractions, we can achieve complexity proportional to the number of terms in the continued fraction of the answer, which is at worst O(log(d)) (where d is the smallest denominator). That may be too optimistic for 2D, but could polylog(d) be achievable? –  Darsh Ranjan Oct 15 '09 at 6:04

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.