Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.05178 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929746168774656 |
|---|---|
| author | Bergold, Helena Das, Arun Kumar Lauff, Robert Scheucher, Manfred Schröder, Felix Sieper, Marie Diana |
| author_facet | Bergold, Helena Das, Arun Kumar Lauff, Robert Scheucher, Manfred Schröder, Felix Sieper, Marie Diana |
| contents | We address the problem of computing the minimum number of triangles to separate a set of blue points from a set of red points in $\mathbb{R}^2$. A set of triangles is a \emph{separator} of one color from the other if every point of that color is contained in some triangle and no triangle contains points of both colors. We consider several variants of the problem depending on whether the triangles are allowed to overlap or not and whether all points or just the blue points need to be contained in a triangle. We show that computing the minimum cardinality triangular separator of a set of blue points from a set of red points is NP-hard and further investigate worst case bounds on the minimum cardinality of triangular separators for a bichromatic set of $n$ points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05178 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Triangular Separation of Bichromatic Point Sets Bergold, Helena Das, Arun Kumar Lauff, Robert Scheucher, Manfred Schröder, Felix Sieper, Marie Diana Computational Geometry We address the problem of computing the minimum number of triangles to separate a set of blue points from a set of red points in $\mathbb{R}^2$. A set of triangles is a \emph{separator} of one color from the other if every point of that color is contained in some triangle and no triangle contains points of both colors. We consider several variants of the problem depending on whether the triangles are allowed to overlap or not and whether all points or just the blue points need to be contained in a triangle. We show that computing the minimum cardinality triangular separator of a set of blue points from a set of red points is NP-hard and further investigate worst case bounds on the minimum cardinality of triangular separators for a bichromatic set of $n$ points. |
| title | On Triangular Separation of Bichromatic Point Sets |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2503.05178 |