# Pixel Approximation of Circle

Dunno whether this is a good problem for MO anyway. Well, here it goes: On a screen you have only little squares, so a natural question is which n-omino approximates a circle best. The problem is less finding a solution but more to find a valid measure for the circle-ness of a n-omino. Boundary length is obviously no good. Boundary length of the convex hull seems better - only that the hull tends to go across Eric-Half-A-Pixel and I'd prefer a measure that could be defined in taxicab geometry. Suggestions?

-
Who is Eric? You have to put some effort to make your problem mathematically clear. And I removed the weird tags which had not been used before. – Wadim Zudilin Jul 3 '11 at 13:51
You might look for "circularity measures" in the area knows as computational metrology. E.g., "Shape based circularity measures of planar point sets"; "Measure of circularity for parts of digital boundaries and its fast computation"; "Discrete circularity measure"; etc. – Joseph O'Rourke Jul 3 '11 at 13:53
Eric-Half-a-Pixel is a reference to this Monty Python sketch maudlin.videosift.com/video/Monty-Python-Eric-the-Half-A-Bee . I don't know any answer to the primary question, but it strikes me as a reasonable one. I imagine David Eppstein will have something valuable to say. – David Speyer Jul 3 '11 at 14:36
I don't know if this is the `best' approximation, since it is unclear what the OP means by this, but the Bresenham approximation is pretty easy to construct: en.wikipedia.org/wiki/Midpoint_circle_algorithm – Mikola Jul 3 '11 at 23:00
@Mikola - yes, this looks sensible. (Maybe not also optimal in the sense implied by Joseph, but "close enough".) THX! – Hauke Reddmann Jul 4 '11 at 10:21