Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '11 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 '11 at 13:53
3  
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.