Optimal Discretization is Fixed-parameter Tractable
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914388425834496 |
|---|---|
| author | Kratsch, Stefan Masařík, Tomáš Muzi, Irene Pilipczuk, Marcin Sorge, Manuel |
| author_facet | Kratsch, Stefan Masařík, Tomáš Muzi, Irene Pilipczuk, Marcin Sorge, Manuel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2003_02475 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Optimal Discretization is Fixed-parameter Tractable Kratsch, Stefan Masařík, Tomáš Muzi, Irene Pilipczuk, Marcin Sorge, Manuel Data Structures and Algorithms Computational Geometry Discrete Mathematics 68Q25, 68W40, 68R01 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. |
| title | Optimal Discretization is Fixed-parameter Tractable |
| topic | Data Structures and Algorithms Computational Geometry Discrete Mathematics 68Q25, 68W40, 68R01 |
| url | https://arxiv.org/abs/2003.02475 |