Return to Answer

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.

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 here 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 $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.

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 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 at the edges of 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.

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.

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.

If you take a hexagonal packing of discs and slightly increase the discs then enclose the packing in a large regular square inside the square the ration 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 discs see http://en.wikipedia.org/wiki/Hexagonal_tiling and look at the one uniform three coloring. There may be a disparity at the edges of 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.

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 hexagonal lattice.

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 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 at the edges of 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.

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.