3
$\begingroup$

So there's a figure which contains n squares of 1 x 1, and I have to find the smallest circumference possible. I don't know if there's an algorithm behind this, I've been stuck on this for two hours but can't figure a working algorithm.

I do know that the smallest circumference of four squares is 8, of 11 is 14 and 200 is 58. If anyone could give me a hint on where to begin, I'd greatly appreciate it.

Improve this question
$\endgroup$
6
  • $\begingroup$ By circumference, do you mean perimeter? $\endgroup$
    – Ilya Bogdanov
    Commented Oct 6, 2019 at 20:14
  • $\begingroup$ Yes sorry it's unclear $\endgroup$
    – Jimmy
    Commented Oct 7, 2019 at 17:01
  • 1
    $\begingroup$ Are squares required to have integral coordinates? If so this is an integer-valued sequence, which you can look for at OEIS by inputting the first few terms you know. $\endgroup$
    – YCor
    Commented Oct 9, 2019 at 5:04
  • 2
    $\begingroup$ And it is sequence A027709 "Minimal perimeter of polyomino with n square cells" where you will find more information and references. In particular the formula 2*ceiling(2*sqrt(n)) is a "working algorithm". $\endgroup$
    – Chris Wuthrich
    Commented Oct 9, 2019 at 11:31
  • $\begingroup$ How, Jimmy, do you know that the answers for $11$ and $200$ squares is $14$ and $58$? $\endgroup$
    – Gerry Myerson
    Commented Oct 10, 2019 at 9:34

1 Answer 1

Reset to default
1
$\begingroup$

Some best known results are shown here: https://erich-friedman.github.io/packing/squincir/

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I don't think this answers the question. OP asks about perimeter of the union of squares, not about the smallest circle containing the union. $\endgroup$
    – YCor
    Commented Oct 9, 2019 at 5:01
  • $\begingroup$ I wondered about that, but the value 14 for 11 squares seems to match the circumference in the link. $\endgroup$
    – RobPratt
    Commented Oct 9, 2019 at 5:10
  • $\begingroup$ Where in the link do you read this? for 11 squares I read "r = 2.214+". $\endgroup$
    – YCor
    Commented Oct 9, 2019 at 5:19
  • $\begingroup$ Multiplying that radius by $2\pi$ gets a circumference that is close to 14, but the OP has now confirmed that he instead meant perimeter. $\endgroup$
    – RobPratt
    Commented Oct 9, 2019 at 12:18

Not the answer you're looking for? Browse other questions tagged .