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)
