Optimal Discretization is Fixed-parameter Tractable

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

TL;DR

This paper settles a long-standing open question in computational geometry by proving that the Optimal Discretization problem is Fixed-Parameter Tractable (FPT). The authors present an algorithm that can separate two sets of points in a plane using the minimum number of axis-parallel lines in $2^{O(k^2 \log k)} n^{O(1)}$ time, where $k$ is the number of lines.

What Problem Does This Paper Address?

Imagine you have a plane scattered with red and blue dots. You want to draw a grid of horizontal and vertical lines such that every resulting rectangular cell contains dots of only one color (or no dots at all). To keep things simple and efficient—perhaps for a machine learning model or a database index—you want to use the minimum total number of lines.

This is the Optimal Discretization problem. While it sounds simple, it is a classic challenge in geometry:

  1. It’s Hard: The problem is NP-complete and APX-hard, meaning we can't find the perfect solution in polynomial time (unless P=NP), and even finding a "good enough" approximation is difficult.
  2. The Parameterized Gap: Researchers wondered if the problem becomes "easy" if the number of lines ($k$) we need is small. This is the realm of Fixed-Parameter Tractability (FPT). Until this paper, it was unknown if an algorithm existed that could solve the problem in time where the "explosion" only depends on $k$, not the total number of points $n$.

Methods

The authors solve this by transforming a geometric problem into a logic problem. Their approach follows a sophisticated pipeline:

  1. Approximation & Layout Guessing: They start with a known 2-approximation of the solution. They then "guess" the general layout—specifically, how many lines of the true optimal solution fall between the lines of the approximation.
  2. Constraint Satisfaction Problem (CSP) Formulation: They translate the requirement of "separating points" into a CSP. In this framework, the positions of the lines are variables, and the points create constraints on where those lines can be placed.
  3. The "Forest CSP": The core technical contribution is identifying and solving a specific type of CSP they call Forest CSP. In this model:
  4. Variables are nodes in a forest (a collection of trees).
  5. Constraints are either "downwards-closed" (if a pair of values works, any "smaller" pair also works) or "segment reversions" (which handle the complex ways point blocks can shift as lines move).
  6. Combinatorial Branching: Instead of relying on heavy "meta-theorems" (like those involving twin-width), the authors develop a custom, singly-exponential branching algorithm to solve the Forest CSP.

Datasets

As a theoretical computer science paper, no empirical datasets or benchmarks were used. The results are established through mathematical proofs and algorithmic complexity analysis. The "input" is treated as any arbitrary set of $n$ points in a 2D plane.

Key Insights and Ideas

  • Taming Ternary Constraints: Usually, separating points involves three or more variables (ternary constraints), which are notoriously hard to solve. The authors discovered that by tracking the "leaders" (the extremal points) of point clusters, they could break these down into simpler binary constraints.
  • The "Aha" Moment on Monotonicity: They realized that as you slide a vertical line across the plane, the way it partitions points into blocks changes in a predictable, monotonic way. This allowed them to use "segment reversions" to model how the "correct" positions for horizontal lines shift in response to vertical ones.
  • Isolation of Tractability: The authors argue that the Forest CSP is an "island of tractability." By reducing Optimal Discretization to this specific CSP, they show that the geometric complexity is actually hiding a structured logical problem.

Key Results

  • FPT Status: The paper proves Optimal Discretization is FPT with respect to the number of lines $k$.
  • Complexity: The algorithm runs in $2^{O(k^2 \log k)} n^{O(1)}$ time. This is a significant improvement over previous "brute force" approaches that would take $n^{O(k)}$ time.
  • Theoretical Closure: The result confirms a conjecture by Bonnet et al. (2017) and contrasts with the Rectangle Stabbing problem, which is known to be much harder (W[1]-hard).

Limitations and Future Work

  • The Exponent: While the algorithm is FPT, the $k^2$ in the exponent means it is still computationally expensive for even moderate values of $k$. The authors suggest that improving the parametric factor to $2^{o(k^2)}$ is a major challenge.
  • Polynomial Kernels: The authors raise the question of whether a "polynomial kernel" exists—a way to shrink the input points into a much smaller set (depending only on $k$) before running the heavy algorithm.
  • Generalization: The FPT result relies strictly on axis-parallel lines. If lines are allowed to have arbitrary slopes, the problem becomes W[1]-hard, meaning an FPT algorithm is unlikely to exist. Exploring the boundary between these two cases remains an open area for 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},
}

Loading related content...

Figure