Optimal Discretization is Fixed-parameter Tractable

Given two disjoint sets W1 and W2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W1 from W2, that is, in every region into which the lines partition the plane there are either only points of W1, or only points of W2, 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 W1 × W2 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.