S. Kratsch, T. Masarík, I. Muzi, M. Pilipczuk, M. Sorge:

"Optimal Discretization is Fixed-parameter Tractable";

Talk: ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia, U.S.; 2021-01-10 - 2021-01-13; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)", ACM, (2021), ISBN: 978-1-61197-646-5; 1702 - 1720.

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 2O(k2 log k)nO(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 axisparallel.

http://dx.doi.org/10.1137/1.9781611976465.103

https://publik.tuwien.ac.at/files/publik_300331.pdf

Created from the Publication Database of the Vienna University of Technology.