MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 edited body

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 phrazed 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)
show/hide this revision's text 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 phrazed 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)