Greedy Monochromatic Island Partitions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911781165727744 |
|---|---|
| author | Broek, Steven van den Meulemans, Wouter Speckmann, Bettina |
| author_facet | Broek, Steven van den Meulemans, Wouter Speckmann, Bettina |
| contents | Constructing partitions of colored points is a well-studied problem in discrete and computational geometry. We study the problem of creating a minimum-cardinality partition into monochromatic islands. Our input is a set $S$ of $n$ points in the plane where each point has one of $k \geq 2$ colors. A set of points is monochromatic if it contains points of only one color. An island $I$ is a subset of $S$ such that $\mathcal{CH}(I) \cap S = I$, where $\mathcal{CH}(I)$ denotes the convex hull of $I$. We identify an island with its convex hull; therefore, a partition into islands has the additional requirement that the convex hulls of the islands are pairwise-disjoint. We present three greedy algorithms for constructing island partitions and analyze their approximation ratios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13340 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Greedy Monochromatic Island Partitions Broek, Steven van den Meulemans, Wouter Speckmann, Bettina Computational Geometry Constructing partitions of colored points is a well-studied problem in discrete and computational geometry. We study the problem of creating a minimum-cardinality partition into monochromatic islands. Our input is a set $S$ of $n$ points in the plane where each point has one of $k \geq 2$ colors. A set of points is monochromatic if it contains points of only one color. An island $I$ is a subset of $S$ such that $\mathcal{CH}(I) \cap S = I$, where $\mathcal{CH}(I)$ denotes the convex hull of $I$. We identify an island with its convex hull; therefore, a partition into islands has the additional requirement that the convex hulls of the islands are pairwise-disjoint. We present three greedy algorithms for constructing island partitions and analyze their approximation ratios. |
| title | Greedy Monochromatic Island Partitions |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2402.13340 |