Nice! I think generating the candidate point is not easy. You can do it with gcd algorithm (essentially) - see http://sarielhp.org/p/97/dhull/dch.pdf. There might be an easier way to do it but I don't see it.
Also ch edges might have vertices in the middle of them - this needs handling but it is not hard...
+Sariel Har-Peled sure, if you start with the edge and no additional information. But you do have additional information, from the previous edge it came from, that allows you to jump-start the rational approximation algorithm.
+Sariel Har-Peled Ok, I implemented it and tested it up to r=100: see http://www.ics.uci.edu/~eppstein/PADS/IntegerPoints.py Part of the trick to getting constant time per point is to maintain a candidate for each hull edge that is in a rectangle with that edge as a side and with the closest parallel grid line as the opposite side, even when there are other points beyond the hull edge but outside the rectangle that are closer (as sometimes happens). This is safe, because each successively generated point will necessarily be in one of these rectangles. And (as the box subroutine of the code shows) when the hull grows, it allows the new candidate point for each of the new edges to be calculated in constant time, essentially by doing only a single step of the (multiplicative) Euclidean gcd algorithm.
I wouldn't be surprised. You can get constant space and O(n^epsilon) time per point by factoring the integers from 1 to n^2, using the factorization to test whether they can be a squared distance (a numbers for which all prime factors that are 3 mod 4 divide an even number of times) and then also using the factorization to generate the points with that distance. Or you can use Eratosthenes to generate the sequence of factored integers without individually factoring them, but that seems to need lots of space again...
Also ch edges might have vertices in the middle of them - this needs handling but it is not hard...
Part of the trick to getting constant time per point is to maintain a candidate for each hull edge that is in a rectangle with that edge as a side and with the closest parallel grid line as the opposite side, even when there are other points beyond the hull edge but outside the rectangle that are closer (as sometimes happens). This is safe, because each successively generated point will necessarily be in one of these rectangles. And (as the box subroutine of the code shows) when the hull grows, it allows the new candidate point for each of the new edges to be calculated in constant time, essentially by doing only a single step of the (multiplicative) Euclidean gcd algorithm.
http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares