Return to Answer

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

• To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
• To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs.

The "neighbor" relation defines a planar graph with $V=n$ vertexes. Euler's formula implies that in a planar graph (with at least 3 vertexes) the number of edges is bounded by: $E\leq 3V-6$. Hence, the number of holes is at most $2n-4$. Hence, $G(n)\leq 3n-4$.

The lower bound gives the tiling shown on the figure

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

• To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
• To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs.

The "neighbor" relation defines a planar graph with $V=n$ vertexes. Euler's formula implies that in a planar graph (with at least 3 vertexes) the number of edges is bounded by: $E\leq 3V-6$. Hence, the number of holes is at most $2n-4$. Hence, $G(n)\leq 3n-4$.

The lower bound gives the tiling shown on the figure:

In the infinite tiling, each hexagon touches 6 holes and each holes touches 3 hexagons, so the number of holes is exactly $2n$. In the finite tiling, the number of holes is smaller since the holes near the boundary can be attached to their neighboring hexagons. So the number of holes is $2n-o(n)$ and $G(n)\geq 3n-o(n)$.

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

• To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
• To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs.

The neighborhood sets form a planar graph, so the number of "neighboring" is (at most) approximately $3n$.

  Hence the number of holes is (at most) approximately $2n$.

The lower bound gives the tiling shown on the figure

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

• To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
• To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs.

The "neighbor" relation defines a planar graph with $V=n$ vertexes. Euler's formula implies that in a planar graph (with at least 3 vertexes) the number of edges is bounded by: $E\leq 3V-6$. Hence, the number of holes is at most $2n-4$. Hence, $G(n)\leq 3n-4$.

The lower bound gives the tiling shown on the figure

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Lets call two sets $C_i$ and $C_j$ neighbors, if they form a neighborhood sides of a some hole. Note that to each hole correspond at least 3 pairs of neighborhood sets, and to each pair of neighborhood sets correspond at most two holes. The neighborhood sets form a planar graph, so the number of "neighbouring" is (at most) approximately three times n. So we get an upper bound.

The lower bound gives the tiling shown on the figure

I think the number of holes is not greater than two times the number of sets $C_i$.

Note that the sets $C_i$ can be extended to $E_i$ in a such way that all holes will be convex (see page 8 in paper of Rom Pinchasi, On the perimeter of $k$ pairwise disjoint convex bodies contained in a convex set in the plane. http://www2.math.technion.ac.il/~room/ps_files/perim_k_convex.pdf). Lets think about $C_i$ as about already extended sets.

Each side of a hole is formed by one of the $C_i$-s. Lets call two sets $C_i$ and $C_j$ neighbors, if they form two adjacent sides of some hole. Note that:

• To each hole correspond at least 3 neighbor-pairs - since each hole has at least 3 sides.
• To each neighbor-pair $C_i,C_j$ correspond at most two holes - since all such holes must have a side co-linear with the segment in which the boundaries of $C_i$ and $C_j$ intersect.

Therefore, the number of holes is at most 2/3 the number of neighbor-pairs. 

The neighborhood sets form a planar graph, so the number of "neighboring" is (at most) approximately $3n$.

Hence the number of holes is (at most) approximately $2n$.

The lower bound gives the tiling shown on the figure