The problem of drawing an approximate circle on an integer x — у grid has a unique best solution in practical cases. If the center is (0, 0) and the square of the radius (r2) is integral, then each grid line that intersects the circle contains near each intersection a unique grid point that simultaneously minimizes (1) the residual x2 + y2 — r2, (2) Euclidean distance to the circle, and (3) displacement along the grid line from the intersection. Thus the set of such minimizing points is the "best" approximation to the circle in several natural senses. Criteria (l)-(3) collectively, but not severally, define unique approximate circles when half-integer center coordinates and integer squared diameters (4r2) are admitted. In other cases the criteria may disagree. Simple, efficient, all-integer algorithms for drawing circles and arcs with approximately known endpoints follow from the analysis. Diophan-tine problems arise in connection with the occasional appearance of sharp (90°) corners in the resulting approximations.
Categories and Subject Descriptors: 1.3.3 [Computer Graphics]: Picture/Image Generation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems— geometric problems and computations
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Raster graphics, diophantine approximation
