MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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 . 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: – 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

Your Answer


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

Browse other questions tagged or ask your own question.