On Triangular Separation of Bichromatic Point Sets

Helena Bergold, Arun Kumar Das, Robert Lauff, Manfred Scheucher, Felix Schröder, Marie Diana Sieper · 2025

Read On Triangular Separation of Bichromatic Point Sets by Helena Bergold, Arun Kumar Das, Robert Lauff, Manfred Scheucher, Felix Schröder, Marie Diana Sieper (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05178.txt.

Introduction

Helena Bergold and co-authors ask how few triangles it takes to fence off one color of points from another, in a 2025 paper. Picture red and blue dots scattered on a page. A separator is a set of triangles that covers all points of one color while never enclosing a point of the other. Fewer triangles means a simpler fence. The team studies several flavors of the problem, with overlapping triangles allowed or not.

Their headline result is a warning: finding the smallest separator is NP-hard, a class of problems with no known fast exact method. They also bound how bad the worst case can be for a set of a given size. The paper is pure math and computing theory. It tells algorithm designers not to hunt for a perfect shortcut here, and it maps the terrain for smarter near-best methods.

Catalog record

CREATORHelena Bergold, Arun Kumar Das, Robert Lauff, Manfred Scheucher, Felix Schröder, Marie Diana Sieper
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Triangular Separation of Bichromatic Point Sets Helena Bergold, Arun Kumar Das, Robert Lauff, Manfred Scheucher, Felix Schröder, Marie Diana Sieper Abstract 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 ℝ 2 \mathbb{R}^{2} . A set of triangles is a 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 all possible 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 n points. 1 Introduction Separability problems on colored point sets are concerned with computing a class of objects of given shapes for a given set of colored points, such that every point of a fixed color is covered with the computed objects and no object contains points of different colors. The exact problem varies depending on the underlying optimizing criteria. We study triangles separating red and blue points in \mathbb{R}^{2} . Separating red and blue points from each other is well studied in computational geometry under the name class cover problems [ 2 , 4 , 7 ] due to their wide applications in data mining, pattern recognition, learning theory, and operations research. The problem is formally defined as follows: Problem 1 ( Overlap-Separation ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of triangles containing all points such that no member of \mathcal{T} contains points of both colors. Note that this problem can be subdivided into two problems. First find the minimum number of triangles \mathcal{T}_{b} containing all the blue points in P such that no triangle in \mathcal{T}_{b} contains a red point. Then compute the minimum number of triangles \mathcal{T}_{r} containing the red, but no blue points. The set \mathcal{T}_{b}\cup\mathcal{T}_{r} is an optimal solution for Problem 1 . Thus it is enough to solve this: Problem 2 ( Overlap-Separation-of-blue ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of triangles containing all blue but no red points of P . However once the triangles are not allowed to intersect each other, the problem becomes more restricted and spawns two different problems for separating the points as follows. Problem 3 ( Disjoint-Separation ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of disjoint triangles containing all points such that no member of \mathcal{T} contains points of both colors. Problem 4 ( Disjoint-Separation-of-blue ) . Input: A set of red and blue points P in \mathbb{R}^{2} . Output: A minimum set \mathcal{T} of disjoint triangles containing all blue but no red points of P . Researchers addressed the problem of computing the minimum number of separators for a bichromatic point set. Canon and Cowen [ 4 ] first considered the problem of finding the minimum number of circles to separate a bichromatic point set in a general metric space. They proved that computing the minimum number of circles centered at the blue points to separate them from the red ones is NP-hard and presented a (\ln n+1) -factor approximation algorithm and devised a PTAS for the problem in \mathbb{R}^{d} . Bereg et al. [ 3 ] showed that computing the minimum number of axis-parallel rectangles to separate a bichromatic planar point set is NP-hard. In the same paper, they addressed the problem of separating objects by vertical or horizontal strips and presented a \mathcal{O}(r\log r+b\log b+\sqrt{rb}) -time exact algorithm where r and b are the numbers of red and blue points respectively. They also proved separation to be NP-hard if the separating objects are half-strips/squares and presented \mathcal{O}(1) -approximations. But separation and partition problems are not only interesting on the algorithmic side. Motivated by a question of Aharoni and Saks, Dumitrescu et al. [ 8 , 9 , 10 ] showed that every bichromatic set of n points can be partitioned into \lfloor\frac{n}{2}\rfloor+1 monochromatic subsets with disjoint convex hulls. This is not true if the subsets have a maximum size of 2. They give an algorithm to find a matching of size \frac{3}{7}n , but show that a monochromatic matching can in some cases only cover \frac{94}{95}n points. This is in contrast to the classic problem of Putnam that every bichromatic set of n blue and n red points admits a perfect matching of the red and the blue points ( [ 11 ] , for a proof of some generalization, see for instance [ 1 ] ). For both settings, the special case of a maximum size of a matching stabbed by a line with points on a circle has been of both long-term and recent interest under the name "necklace folding problem" [ 5 , 12 ] . cover both cover blue disjoint \geq\lfloor\frac{n}{2}\rfloor+1 ( Proposition B.1 ) \geq\lfloor\frac{n}{4}\rfloor+1 ( Proposition B.17 ) \leq\lfloor\frac{n}{2}\rfloor+1 ( Proposition B.3 ) \leq\lfloor\frac{2}{7}n\rfloor+1 ( Proposition B.9 ) overlap \geq\frac{3}{8}n-\Oh(1) ( Proposition B.17 ) \geq\lfloor\frac{n}{4}\rfloor+1 ( Proposition B.17 ) \leq\frac{13}{30}n+\Oh(1) ( Proposition B.5 ) \leq\frac{4}{15}n+\Oh(1) ( Proposition B.15 ) Table 1 : Summary of bounds on triangles separating bichromatic planar point sets of n points in total. We show that Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . are NP-hard. Then we prove combinatorial bounds on the number of triangles required for the problems in the worst case for n points, see Table 1 . The paper is organized in the following manner. Section 2 describes the hardness of the problems by a polynomial time reduction from the Planar Monotone 3-SAT problem. Section 3 presents an overview of the combinatorial results. Finally, the paper is concluded in Section 4 . For detailed proofs we refer to the Appendix. 2 NP-hardness We present a polynomial-time reduction from the known NP-hard Planar Monotone (PM) 3-SAT [ 6 ] to the problems Problem 2 ( Overlap-Separation-of-blue ) . and Problem 4 ( Disjoint-Separation-of-blue ) . (Problems 2 and 4 ). PM 3-SAT is a special version of 3-SAT , where the usual boolean formula \phi is in conjunctive normal form, each clause contains 3 literals and all of them are either positive or negative. Moreover, there exists a planar embedding \Gamma_{\phi} of the incidence graph of \phi , in which the variables lie on the x -axis, the clauses with positive literals are above the x -axis and the clauses with negative literals are below the x -axis. Given a PM 3-SAT formula \phi , we construct a set of bichromatic points in the plane such that we can decide whether \phi is satisfiable based on the number of triangles in a minimum separator. The condition holds whether the triangles are allowed to overlap or not. Thus we simultaneously address the

Read the complete text