Abstract: Given two disjoint sets $W_1$ and $W_2$ of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate $W_1$ from $W_2$. This is equivalent to discretizing continuous variables into as few segments as possible while ensuring no pair of points from different sets are projected onto the same segment pair. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines $k$, running in $2^{O(k^2 \log k)} n^{O(1)}$ time. This result settles a question by Bonnet et al. [IPEC 2017] and contrasts with the intractability of related generalizations like Rectangle Stabbing.
Introduction
Imagine a plane scattered with two distinct sets of points, such as red and blue dots. The Optimal Discretization problem seeks to draw a grid of horizontal and vertical lines such that every resulting rectangular cell contains dots of only one color or remains empty. The objective is to achieve this separation using the minimum total number of lines.
While conceptually simple, the problem is NP-complete and APX-hard. Historically, it was unknown whether the problem was Fixed-Parameter Tractable (FPT)—that is, whether an algorithm exists where the computational complexity's exponential growth depends solely on the number of lines $k$, rather than the total number of points $n$.
Methods
The authors resolve this by transforming the geometric challenge into a structured logic problem through a multi-stage pipeline:
- Layout Guessing: The process begins with a known 2-approximation of the solution to "guess" the general layout of the optimal lines.
- Constraint Satisfaction Problem (CSP) Formulation: The requirement to separate points is translated into a CSP. Here, line positions are variables, and the points themselves define the constraints on where these lines can be placed.
- The Forest CSP: The core contribution is identifying a specific "Forest CSP" where variables are nodes in a forest. Constraints are modeled as "downwards-closed" or "segment reversions" to handle how point blocks shift as lines move.
- Combinatorial Branching: Instead of generic meta-theorems, the authors developed a custom, singly-exponential branching algorithm to solve the Forest CSP.
Key Insights
- Taming Ternary Constraints: Separating points typically involves complex ternary constraints (involving three or more variables). The authors simplified these into binary constraints by tracking the "leaders" (extremal points) of point clusters.
- Monotonicity and Segment Reversions: The researchers observed that as a vertical line slides across the plane, the partitioning of points changes monotonically. This allows "segment reversions" to model how horizontal line positions must shift in response to vertical ones.
- Islands of Tractability: By reducing the geometric problem to the Forest CSP, the authors demonstrated that the underlying complexity of Optimal Discretization is governed by a highly structured logical framework.
Results and Complexity
The paper successfully proves that Optimal Discretization is FPT with respect to the number of lines $k$. The resulting algorithm runs in $2^{O(k^2 \log k)} n^{O(1)}$ time. This is a significant theoretical improvement over previous brute-force approaches that required $n^{O(k)}$ time. This result confirms a conjecture by Bonnet et al. (2017) and highlights a sharp boundary in tractability: while axis-parallel discretization is FPT, the problem becomes W[1]-hard if lines are allowed arbitrary slopes.
Future Work
Despite achieving FPT status, the $k^2$ factor in the exponent remains computationally expensive for large $k$. Future research may focus on whether the parametric factor can be improved to $2^{o(k^2)}$ or if a "polynomial kernel" exists to shrink the input size before processing. Additionally, exploring the boundary between axis-parallel and arbitrary-slope cases remains a fertile ground for geometric complexity research.
Summary updated