Skip to main content
3 of 4
added detail
Kristal Cantwell
  • 6.5k
  • 1
  • 25
  • 45

If you take a triangular packing of discs and slightly increase the radius of each disc then enclose the packing in a large regular square and remove all discs outside the square. Then inside the square the ratio of discs to regions outside the discs will be two to one since there is a hexagonal tiling with a three coloring such that one color is assigned to the discs and two colors are assigned to regions not in the discs and each coloring has the same number of hexagons see http://en.wikipedia.org/wiki/Hexagonal_tiling and look at the one uniform three coloring. There may be a disparity near the sides the square but that will be linear and the number of discs inside a square will be quadratic so any bound other than 2n will be exceeded by increasing the size of the square.

So the upper bound will not be n or any constant less than 2 and greater than one times n plus another constant. I don't know how close to 2n-4 you can get though or if there is an improvement to the triangular lattice.

Kristal Cantwell
  • 6.5k
  • 1
  • 25
  • 45