[Darsh](http://math.berkeley.edu/~dranjan/) asked over at the [20 questions seminar](http://scratchpad.wikia.com/wiki/20qs):


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



How can you find small denominators inside triangles?
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)


