Welcome to MathOverflow

Question

0

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?

edited Jul 3 2011 at 13:50

Wadim Zudilin
8,674●1●24●59

asked Jul 3 2011 at 13:45

Hauke Reddmann
1,081●2●9

1

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 2011 at 13:51

1

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 2011 at 13:53

3

Eric-Half-a-Pixel is a reference to this Monty Python sketch maudlin.videosift.com/video/… . 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 2011 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 2011 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 2011 at 10:21

Pixel Approximation of Circle

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.