Optimal Discretization is Fixed-parameter Tractable

Stefan Kratsch, Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Manuel Sorge

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.

Separating red and blue point sets using a grid of axis-parallel 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:

  1. Layout Guessing: The process begins with a known 2-approximation of the solution to "guess" the general layout of the optimal lines.
  2. 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.
  3. 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.
  4. Combinatorial Branching: Instead of generic meta-theorems, the authors developed a custom, singly-exponential branching algorithm to solve the Forest CSP.
Geometric constraints translated into logical predicates for the CSP formulation.

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

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$, that is, in every region into which the lines partition the plane there are either only points of $W_1$, or only points of $W_2$, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of $x$-coordinates and the range of $y$-coordinates into as few segments as possible, maintaining that no pair of points from $W_1 \times W_2$ are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time $2^{O(k^2 \log k)} n^{O(1)}$, where $k$ is the bound on the number of lines to find and $n$ is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.
BibTeX
@inproceedings{kratsch2021optimal,
  author = {Stefan Kratsch and Tomás Masarík and Irene Muzi and Marcin Pilipczuk and Manuel Sorge},
  title = {{Optimal Discretization is Fixed-parameter Tractable}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=5bUj1EKGtU},
}
Figure