Bichromatic Classifications of Points Using Strips

The strip model is a natural and powerful geometric representation of separation. Unlike a single separating line, which represents a zero-width decision boundary, a strip provides a thickened boundary that captures a tolerance margin around a linear separator. This model represents situations in which the target set must lie within a bounded corridor that remains free of extraneous or adversarial points. Such a representation is essential when the target data corresponds to a physical object, a high-confidence cluster, or a region that must be certified safe within a specified geometric width [19]. Optimizing the placement of such a strip allows one to quantify the structural purity of a dataset and determine how much perturbation can be tolerated before separation becomes impossible. In this sense, strip separability serves as a robust geometric analogue of margin-based classification.

This geometric formulation arises naturally in several application domains requiring high-precision spatial reasoning. In metrology and industrial design, strip containment models tolerance-zone analysis: a manufactured component must lie within an allowable corridor while avoiding forbidden regions occupied by other parts [33]. In robotics and motion planning, strip separation captures narrow-passage navigation problems, where a robot must follow a collision-free linear trajectory that accounts for its physical width while avoiding obstacles. In pattern recognition and machine learning, strip separation corresponds to margin-based classification, where maximizing the width of a separating strip improves robustness and generalization [32]. Similarly, in geographic information systems and urban planning, strips model buffer zones that must fully contain protected regions while remaining disjoint from hazardous or restricted areas. These examples illustrate that strips provide a minimal yet expressive geometric primitive for modeling safety margins, tolerances, and robustness constraints.

Furthermore, we consider natural generalizations of MaxBlue and MinRed, in which up to $t$ parallel strips are allowed for the separation, for a fixed integer $t$. Extending from a single strip to multiple parallel strips is both natural and essential for modeling structured data in which target points occur in several roughly parallel groups separated by gaps or forbidden regions. Such patterns arise in applications like crop-row detection [22], multi-lane traffic modeling [18], and circuit layout verification [23]. A single strip cannot capture these interleaved configurations, whereas multiple strips allow the model to represent periodicity and spacing, yielding a more expressive separability that maximizes covered target points while strictly excluding forbidden ones. This formulation is a discrete analogue of maximum-margin separation for nonconvex distributions, related to classical geometric separability and covering problems [26, 31].

See Figure 1 for an illustration of each problem.

We can solve MaxBlue by solving MaxBlue^∗. Let $P^{\ast }=B^{\ast }\cup R^{\ast }$ be a set of $n$ lines in the plane. Our algorithm is rather simple. It computes a vertical segment in each cell $C$ of $𝒜(R^{\ast })$ that intersects the most lines in $B^{\ast }$. Among all such segments, it reports the one that intersects the most. An optimal vertical segment intersects no lines in $R^{\ast }$, which ensures the algorithm’s correctness. However, achieving the optimal running time is challenging.

We describe the algorithm in detail and analyze its time complexity. Consider the arrangements $𝒜(R^{\ast })$ and $𝒜(P^{\ast })$. Note that once $𝒜(P^{\ast })$ is computed, the arrangement $𝒜(R^{\ast })$ is implicitly available. Let $C$ be a cell of $𝒜(R^{\ast })$. Imagine we sweep $C$ with a vertical line $\mathrm{\ell }$ from left to right, starting from the leftmost vertex of $C$. Let $c_B$ be the number of lines in $B^{\ast }$ whose intersection with $\mathrm{\ell }$ lies in the interior of $C$. Observe that $c_B=0$ at the leftmost vertex of $C$, and $c_B$ changes only when $\mathrm{\ell }$ hits an intersection point $x$ between a line $h$ in $B^{\ast }$ and the boundary of $C$, excluding the leftmost and rightmost vertices: $c_B$ increases by one if $h$ enters $C$ at $x$, and $c_B$ decreases by one if $h$ leaves $C$ at $x$. Thus, we can maintain $c_B$ by traversing the upper and lower boundary chains of $C$ from their leftmost vertex within the arrangement $𝒜(P^{\ast })$, and determine the position of $\mathrm{\ell }$ at which $c_B$ is maximized. We repeat this procedure for every cell in $𝒜(R^{\ast })$.

The arrangement $𝒜(P^{\ast })$ can be computed in $O(n^2)$ time. For each cell $C$ in $𝒜(R^{\ast })$, the procedure above takes $O(n_C)$ time, where $n_C$ denotes the number of vertices of $𝒜(P^{\ast })$ lying on the boundary of $C$. Let $d(v)$ be the degree of a vertex $v$ in $𝒜(P^{\ast })$, that is, number of edges incident to $v$ in $𝒜(P^{\ast })$. Observe that each vertex $v$ of $𝒜(P^{\ast })$ appears on the boundaries of at most $d(v)$ cells of $𝒜(R^{\ast })$. Thus, the total time complexity is bounded by ${\sum }_{C\in 𝒜(R^{\ast })}O(n_C)={\sum }_{v\in 𝒜(P^{\ast })}O(d(v))=O(n^2)$. $◀$

We show that MaxBlue is 3SUM-hard by a reduction from the GEOMBASE problem. Thus, there is no strongly sub-quadratic algorithm for MaxBlue unless the 3SUM problem can be solved in $O(n^{2-\epsilon })$ time for any $\epsilon >0$. The GEOMBASE problem is defined as follows: Given $n$ points in the plane with integer coordinates on three horizontal lines $y=0$, $y=1$ and $y=2$, determine whether there exists a non-horizontal line containing three of the points. It is known that the GEOMBASE problem is 3SUM-hard [16].

We use a reduction from the GEOMBASE problem. Consider $n$ blue points in the plane with integer $x$-coordinates larger than 0 and at most $M$ on three horizontal lines $y=0$, $y=1$ and $y=2$, for some integer $M$. For each blue point $p=(\alpha ,1)$, we place two red points $q=(\alpha +1/(2\sqrt{4+M^2}),1)$ and $q^{\prime }=(\alpha -1/(2\sqrt{4+M^2}),1)$. We show that no line $\mathrm{\ell }:(b-a)y-2x+2a=0$ passing through any two blue points $(a,0),(b,2)$ intersects $q{q}^{\prime }$ unless it passes through $p$. If $\mathrm{\ell }$ does not pass through $p$, $|2\alpha -a-b|⩾1$ since $\alpha$, $a$, and $b$ are all integers. Then the distance between $p$ and $\mathrm{\ell }$ is $|2\alpha -a-b|/\sqrt{4+{(a-b)}^2}⩾|2\alpha -a-b|/\sqrt{4+M^2}⩾1/\sqrt{4+M^2}>1/(2\sqrt{4+M^2})$. See Figure 4(a).

Similarly, for each $i=0,2$, we place two red points $q,q^{\prime }$ on $y=i$ for each blue point $(\beta ,i)$ such that no line passing through any two blue points $(a,j),(b,k)$ for $\{j,k\}=\{0,1,2\}\setminus \{i\}$ intersects $q{q}^{\prime }$ unless it passes through $(\beta ,i)$. Thus, we have $n$ blue points and $2n$ red points in total. The reduction takes $O(n)$ time.

If a non-horizontal line contains three blue points, there is a strip containing three blue points while excluding any red points. If no such line exists, no strip contains three blue points while excluding any red points. See Figure 4(b). $◀$

In $t$-MaxBlue^∗, we are given a set $P^{\ast }=B^{\ast }\cup R^{\ast }$ of $n$ lines in the plane and an integer $t$, and find $t$ vertical segments with a common $x$-coordinate whose union intersects the maximum number of lines in $B^{\ast }$ while intersecting no lines in $R^{\ast }$. For convenience, we will refer to the lines in $B^{\ast }$ as blue lines and the lines in $R^{\ast }$ as red lines.

We first compute the arrangement $𝒜(R^{\ast }\cup B^{\ast })$ in $O(n^2)$ time. Then, we sweep the plane with a vertical line $\mathrm{\ell }$ from left to right. For any fixed position, $\mathrm{\ell }$ is subdivided by $\mathrm{\ell }\cap R^{\ast }$ into $|R|+1$ segments (possibly open or degenerate to a point). By shrinking those segments, we consider the maximal vertical segments whose endpoints lie on $\mathrm{\ell }\cap B^{\ast }$ and that do not intersect any lines of $R^{\ast }$. See Figure 8. Let $s_1,s_2,\mathrm{\dots },s_{|R|+1}$ denote these segments, ordered by decreasing $y$-coordinate, and let $n_i$ denote the number of blue lines intersected by $s_i$.

During the sweep, we maintain two lists, $L_1$ and $L_2$. List $L_1$ contains pairs $(s_i,n_i)$, sorted by decreasing $y$-coordinate of the segments. List $L_2$ contains the sorted numbers $n_i$. Any combinatorial changes to the vertical segments in $\mathrm{\ell }$ occur only when $\mathrm{\ell }$ hits a vertex of $𝒜(R^{\ast }\cup B^{\ast })$. Any changes to the numbers occur only when $\mathrm{\ell }$ hits an intersection of a blue line and a red line, which is a vertex of $𝒜(R^{\ast }\cup B^{\ast })$. At such an intersection, only two consecutive numbers $n_i$ and $n_{i+1}$ change, each by at most one. In Figure 8, $L_1$ has $(s_2,3)$ and $(s_3,2)$ at ${\mathrm{\ell }}_1$, but they change to $(s_2,2)$ and $(s_3,3)$ at ${\mathrm{\ell }}_2$ due to the intersection $u$. After ${\mathrm{\ell }}_4$, $s_2$ intersects no blue lines, and $L_1$ has $(s_2,0)$. Let an event refer to a moment when $\mathrm{\ell }$ hits a vertex of $𝒜(R^{\ast }\cup B^{\ast })$.

By maintaining a balanced binary search tree that stores $R^{\ast }\cup B^{\ast }$ in sorted order of their intersections with $\mathrm{\ell }$, as in a standard plane sweep algorithm, we can compute all events sorted in their $x$-coordinates in $O(n^2\log n)$ total time. At an event with a blue line and a red line defining the event, we can update both $L_1$ and $L_2$ in $O(\log n)$ time. Thus, the overall running time is $O(n^2\log n)$.

To find an optimal solution, we maintain an additional value, the sum of the largest $t$ values in $L_2$. The sum can be updated in $O(\log n)$ time per event by maintaining $L_2$. Let $N\subseteq \{n_1,\mathrm{\dots },n_{|R|+1}\}$ be the set of the $t$ largest values in $L_2$, and let $S\subseteq \{s_1,\mathrm{\dots },s_{|R|+1}\}$ be the corresponding segments at a position of $\mathrm{\ell }$ where the sum is maximized. The vertical segments in $S$ intersect ${\sum }_{m\in N}m$ blue lines but no red lines, and $S$ is an optimal solution to $t$-MaxBlue^∗. By the dual transform, the dual of the vertical segments in $S$ are $t$ parallel strips that contain ${\sum }_{m\in N}m$ blue points but no red points. Thus, the set of $t$ parallel strips, dual to $S$, is an optimal solution to $t$-MaxBlue. $◀$

We use a reduction from the GEOMBASE problem. Consider a set of $n$ red points on the horizontal lines $y=0$, $y=1$, and $y=2$, each with an integer $x$-coordinate satisfying for some integer $M$. For each $i=0,1,2$, and for each red point $p=(\beta ,i)$, we place two blue points $q,q^{\prime }$ on $y=i$ as in Theorem 11 in total $O(n)$ time such that no line passing through any two red points $(a,j)$, $(b,k)$ for $\{j,k\}=\{0,1,2\}\setminus \{i\}$ intersects $q{q}^{\prime }$ unless it passes through $p$. We have $n$ red points and $2n$ blue points in total. The reduction takes $O(n)$ time.

Suppose that there exists a non-horizontal line $\mathrm{\ell }$ containing three red points. Then there are two strips parallel to $\mathrm{\ell }$ such that their union contains all blue points while containing exactly $n-3$ red points. If no non-horizontal line contains three red points, no two parallel strips can cover all blue points while excluding three or more red points. In particular, every pair of parallel strips whose union contains all blue points must contain at least $n-2$ red points. $◀$

In the dual plane, we are given a set $P^{\ast }=B^{\ast }\cup R^{\ast }$ of $n$ lines in the plane and an integer $t$. Our goal is to find $t$ vertical segments with a common $x$-coordinate whose union intersects all lines in $B^{\ast }$ while minimizing the number of lines in $R^{\ast }$ intersected by the union.

For a cell $C$ of $𝒜(B^{\ast })$, let ${𝖧}_{𝖴}(C)$ and ${𝖧}_{𝖫}(C)$ denote the upper hull and the lower hull of $C$, respectively. Let $s_1$ and $s_2$ be an optimal pair of vertical segments where $s_1$ lies above $s_2$. Since $s_1\cup s_2$ intersects all lines in $B^{\ast }$, $s_1$ has its upper endpoint on ${𝒜}_{|B|-1}(B^{\ast })$, $s_2$ has its lower endpoint on ${𝒜}_0(B^{\ast })$, and both $s_1$ and $s_2$ are incident to a common cell in $𝒜(B^{\ast })$. See Figure 9(a).

Therefore, for each cell $C$ in $𝒜(B^{\ast })$, except the cell below ${𝒜}_0(B^{\ast })$ and the cell above ${𝒜}_{|B|-1}(B^{\ast })$, we find two vertical segments $s_1$ and $s_2$ such that their endpoints are the intersections between a vertical line and $\{{𝒜}_{|B|-1}(B^{\ast }),{𝖧}_{𝖴}(C),{𝖧}_{𝖫}(C),{𝒜}_0(B^{\ast })\}$, and the number of lines in $R^{\ast }$ intersected by $s_1\cup s_2$ is minimized.

To do this efficiently, we first compute $𝒜(B^{\ast }\cup R^{\ast })$ in $O(n^2)$ time, which also gives $𝒜(B^{\ast })$. For a vertex $v$ in $𝒜(B^{\ast }\cup R^{\ast })$, let $n(v)$ denote the number of lines in $R^{\ast }$ lying above $v$. We can compute $n(v)$ for every vertex $v$ in $𝒜(B^{\ast }\cup R^{\ast })$ in $O(n^2)$ time by traversing the arrangement $𝒜(B^{\ast }\cup R^{\ast })$.

For a cell $C$ in $𝒜(B^{\ast })$, all points in ${𝖧}_{𝖫}(C)$ have the same level in $𝒜(B^{\ast })$, and all points in ${𝖧}_{𝖴}(C)$ have the same level in $𝒜(B^{\ast })$, if they are defined. Their levels differ by one in $𝒜(B^{\ast })$. Let ${𝒞}_i$ denote the set of cells in $𝒜(B^{\ast })$ whose lower hull lies on ${𝒜}_i(B^{\ast })$ for $i=0,\mathrm{\dots },|B|-2$. Then, ${𝒞}_i$ is the set of cells in $𝒜(B^{\ast })$ whose upper hull lies on ${𝒜}_{i+1}(B^{\ast })$. Note that ${\bigcup }_{i=0}^{|B|-2}{𝒞}_i$ is the set of all cells in $𝒜(B^{\ast })$, except the cell below ${𝒜}_0(B^{\ast })$ and the cell above ${𝒜}_{|B|-1}(B^{\ast })$.

Consider ${𝒞}_i$ for a fixed $0⩽i⩽|B|-2$. We find two optimal vertical segments lying on a vertical line $\mathrm{\ell }$, restricted to the cells in ${𝒞}_i$ as follows. Imagine we sweep the plane with a vertical line $\mathrm{\ell }$ from left to right. At a fixed position of $\mathrm{\ell }$, let $s_1$ and $s_2$ be the vertical segments lying on $\mathrm{\ell }$ whose endpoints are the intersections of $\mathrm{\ell }$ and each of the four chains in $\{{𝒜}_{|B|-1}(B^{\ast }),{𝒜}_{i+1}(B^{\ast }),{𝒜}_i(B^{\ast }),{𝒜}_0(B^{\ast })\}$. See Figure 9(b).

Let $v_1\in {𝒜}_{|B|-1}(B^{\ast })$, $v_2\in {𝒜}_{i+1}(B^{\ast })$, $v_3\in {𝒜}_i(B^{\ast })$, and $v_4\in {𝒜}_0(B^{\ast })$ be the rightmost vertices in $𝒜(B^{\ast }\cup R^{\ast })$ among the ones on or left to $\mathrm{\ell }$. Then, the number of lines in $R^{\ast }$ intersected by $s_1\cup s_2$ is $n(v_2)-n(v_1)+n(v_4)-n(v_3)$. Thus, while we slide $\mathrm{\ell }$, the number changes only when $\mathrm{\ell }$ encounters a vertex of $𝒜(B^{\ast }\cup R^{\ast })$ contained in the four chains.

Since $n(v)$ is computed for every vertex $v$ in $𝒜(B^{\ast }\cup R^{\ast })$ in the preprocessing and the total number of vertices in the four chains is $O(n)$, this procedure can be done in $O(n)$ time by traversing the four chains in the arrangement $𝒜(B^{\ast }\cup R^{\ast })$. We repeat this for every $0⩽i⩽|B|-2$, which takes $O(n^2)$ time in total. $◀$

We give a reduction from $t$-MinRed to $(t+1)$-MaxBlue in $O(n)$ time, which completes the proof by Theorem 19. Let $P=B\cup R$ be a set of $n$ points in the plane. Assume that there is an optimal solution for $t$-MinRed whose strips have a positive slope. The other case can be handled symmetrically.

We first compute an axis-parallel square $Q$ that contains $P$ in its interior. Let $v_a$ and $v_b$ be the upper-left and lower-right vertices of $Q$, respectively. Consider two translates $Q_a$ and $Q_b$ of $Q$, one with its lower-right corner at $v_a$ and one with its upper-left corner at $v_b$. Let $v_1,\mathrm{\dots },v_4$ and $v_5,\mathrm{\dots },v_8$ denote the corners of $Q_a$ and $Q_b$, respectively. For each $v_i$, we place $n$ points on it. Let $V$ be the set of $8n$ points placed on $v_1,\mathrm{\dots },v_8$. Observe that the convex hull of $V$ contains the convex hull of $B\cup R$. See Figure 10.

Let $S_{\text{opt}}$ be an optimal solution for $t$-MinRed whose strips have positive slope and contain no point in $V$. Let denote the number of points in $R$ covered by $S_{\text{opt}}$. Let $\overline{S_{\text{opt}}}$ be a set of $t+1$ strips that are parallel and disjoint to the strips of $S_{\text{opt}}$ and whose union covers all points in $(P\cup V)\setminus S_{\text{opt}}$. Since $S_{\text{opt}}$ covers all points in $B$, $\overline{S_{\text{opt}}}$ covers no points in $B$, and it covers $8n+|R|-k_{\text{opt}}$ points in total, $8n$ from $V$ and $|R|-k_{\text{opt}}$ from $R$.

We now construct an instance of $(t+1)$-MaxBlue with two point sets $E=V\cup R$ and $F=B$. Here, an optimal solution consists of $t+1$ parallel strips whose union contains the maximum number of points of $E$ while containing no points of $F$. Let $S$ be an optimal solution for the $(t+1)$-MaxBlue instance. Let $\overline{S}$ be a set of $t$ strips such that each strip is the region between two consecutive strips of $S$.

We show that $\overline{S}$ is an optimal solution for $t$-MinRed for the instance. We first show three observations on $S$: (1) every point in $V$ is covered by $S$, (2) every point in $F=B$ is covered by $\overline{S}$, and (3) every point in $R$ is covered by either $S$ or $\overline{S}$.

For (1), suppose there is a point of $V$ not covered by $S$. Then $S$ covers at most $7n$ points of $V$, and hence at most $7n+|R|$ points of $E=V\cup R$. This contradicts the optimality of $S$, because $\overline{S_{\text{opt}}}$ covers $8n+|R|-k_{\text{opt}}>7n+|R|$ points of $E$ while covering no point of $F=B$.

For (2), suppose there is a point $p\in F=B$ not covered by $\overline{S}$. By definition, $p$ is not covered by $S$, so $p$ lies outside $S\cup \overline{S}$. This implies that some vertex in $V$ is not covered by $S$, contradicting (1). See Figure 10(b).

For (3), suppose there is a point $q\in R$ covered by neither $S$ nor $\overline{S}$. Then we could enlarge an outermost strip of $S$ so that it contains $q$ without including any point of $F=B$, contradicting the optimality of $S$.

By (2), $\overline{S}$ covers all points of $F=B$. Let $k$ be the number of points of $R$ covered by $\overline{S}$. Suppose $\overline{S}$ is not optimal for $t$-MinRed, that is, $k>k_{\text{opt}}$. By (3), $S$ covers $|R|-k$ points of $R$, and by (1), it covers all $8n$ points of $V$. Thus $S$ covers $8n+|R|-k$ points of $E=V\cup R$, which is less than $8n+|R|-k_{\text{opt}}$, contradicting the optimality of $S_{\text{opt}}$. $◀$