Optimal Discretization is Fixed-parameter Tractable

Given two disjoint sets W 1 and W 2 of points in the plane, the O ptimal D iscretization 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, O ptimal D iscretization 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 × 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, 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.

Authors

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

Keywords

No keywords are indexed for this paper.