Timeline for Upperbounding the number of regions induced by a set of unit disks
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 1, 2015 at 20:49 | history | edited | Kristal Cantwell | CC BY-SA 3.0 |
added formatting
|
| Mar 16, 2015 at 22:25 | comment | added | Emil Jeřábek | (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.) | |
| Mar 16, 2015 at 22:04 | comment | added | Emil Jeřábek | 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). | |
| Mar 16, 2015 at 21:08 | comment | added | Kristal Cantwell | 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. | |
| Mar 16, 2015 at 15:32 | comment | added | Emil Jeřábek | 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. | |
| Mar 15, 2015 at 21:24 | vote | accept | 1v0 | ||
| Mar 15, 2015 at 21:24 | vote | accept | 1v0 | ||
| Mar 15, 2015 at 21:24 | |||||
| Mar 15, 2015 at 21:01 | vote | accept | 1v0 | ||
| Mar 15, 2015 at 21:01 | |||||
| Mar 15, 2015 at 20:45 | history | edited | Kristal Cantwell | CC BY-SA 3.0 |
added detail
|
| Mar 15, 2015 at 20:29 | history | edited | Kristal Cantwell | CC BY-SA 3.0 |
corrected word choice
|
| Mar 15, 2015 at 19:50 | history | answered | Kristal Cantwell | CC BY-SA 3.0 |