5
$\begingroup$

Given a set $D$ of $n$ same radius disks, embedded in the plane, their arrangement induces a number $k$ of connected regions in $\mathbb{R}^2 \setminus \cup_{d \in D}$ .

I am interested in an upper bound on $k$ as a function of $n$.

Does anybody know (a reference for) a good upperbound on $k$?

Since the Union Complexity, i.e., the number of arcs on the boundary of $D$ is at most $6n-12$ (if $n \geq 3$) and each connected region is bounded by at least 3 disks, it follows that $k \leq 2n - 4$, but I feel that this bound should be much closer to $n$ than to $2n$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You argument gives a lower bound of the form $2n-O(\sqrt n)$. I believe the $\sqrt n$ term is unavoidable: the $6(n-2)$ bound includes arcs on the outer boundary that do not contribute to the number of regions, and I think there have to be at least a constant multiple of the square root of the number of regions of these outer arcs by some sort of isoperimetric inequality. $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2015 at 15:32
  • $\begingroup$ Your argument would go through unless discs overlapped enough that the total area enclosed by the outer arcs was small enough to cause the isoperimetric inequality to fail. In that case I can't extend the argument or find a counterexample. $\endgroup$
    – Kristal Cantwell
    Commented Mar 16, 2015 at 21:08
  • $\begingroup$ This was just a heuristic, and I don’t know how to make it precise. However, the intuition should be that a bound on the enclosed area should give a bound on the number of regions, or in other words, the density of regions (meaning the number of distinct regions per unit area) in sufficiently large rectangles should be bounded by a constant, on account of the fact that each region is adjacent to a fixed-size chunk devoid of other regions (namely, a disk). $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2015 at 22:04
  • $\begingroup$ (But what I just wrote shouldn’t be taken too literally either. One can have, for example, an arbitrary large number of regions stacked along the boundary of one disk, hence in a bounded area.) $\endgroup$
    – Emil Jeřábek
    Commented Mar 16, 2015 at 22:25

You must log in to answer this question.

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