Tiling with Boundaries: Dense digital images have large connected components
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917142703636480 |
|---|---|
| author | Fridberg, Kyle |
| author_facet | Fridberg, Kyle |
| contents | If most of the pixels in an $n \times m$ digital image are the same color, must the image contain a large connected component? How densely can a given set of connected components pack in $\mathbb{Z}^2$ without touching? We answer these two closely related questions for both 4-connected and 8-connected components. In particular, we use structural arguments to upper bound the "white" pixel density of infinite images whose white (4- or 8-)connected components have size at most $k$. Explicit tilings show that these bounds are tight for at least half of all natural numbers $k$ in the 4-connected case, and for all $k$ in the 8-connected case. We also extend these results to finite images.
To obtain the upper bounds, we define the exterior site perimeter of a connected component and then leverage geometric and topological properties of this set to partition images into nontrivial regions called polygonal tiles. Each polygonal tile contains a single white connected component and satisfies a certain maximality property. We then use isoperimetric inequalities to precisely bound the area of these tiles. The solutions to these problems represent new statistics on the connected component distribution of digital images. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11740 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tiling with Boundaries: Dense digital images have large connected components Fridberg, Kyle Combinatorics Computational Geometry Metric Geometry 52C20, 68U05, 05B45, 05C10 I.3.5; I.4.6; G.2.2 If most of the pixels in an $n \times m$ digital image are the same color, must the image contain a large connected component? How densely can a given set of connected components pack in $\mathbb{Z}^2$ without touching? We answer these two closely related questions for both 4-connected and 8-connected components. In particular, we use structural arguments to upper bound the "white" pixel density of infinite images whose white (4- or 8-)connected components have size at most $k$. Explicit tilings show that these bounds are tight for at least half of all natural numbers $k$ in the 4-connected case, and for all $k$ in the 8-connected case. We also extend these results to finite images. To obtain the upper bounds, we define the exterior site perimeter of a connected component and then leverage geometric and topological properties of this set to partition images into nontrivial regions called polygonal tiles. Each polygonal tile contains a single white connected component and satisfies a certain maximality property. We then use isoperimetric inequalities to precisely bound the area of these tiles. The solutions to these problems represent new statistics on the connected component distribution of digital images. |
| title | Tiling with Boundaries: Dense digital images have large connected components |
| topic | Combinatorics Computational Geometry Metric Geometry 52C20, 68U05, 05B45, 05C10 I.3.5; I.4.6; G.2.2 |
| url | https://arxiv.org/abs/2512.11740 |