[Zurück]

S. Kratsch, T. Masarík, I. Muzi, M. Pilipczuk, M. Sorge:
"Optimal Discretization is Fixed-parameter Tractable";
Vortrag: ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia, U.S.; 10.01.2021 - 13.01.2021; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)", ACM, (2021), ISBN: 978-1-61197-646-5; S. 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