Exact algorithms for optimal discretization

Abstract

The optimal discretization problem asks, given two disjoint sets of points $R$ and $B$ in the plane, for a minimal family of horizontal and vertical lines that separate the two sets, so that no cell delimited by the lines contains points from both sets. The problem arises as a pre-processing in supervised machine learning, and has received significant attention in parameterized algorithmics. Answering the question raised by Bonnet, Giannopoulos, and Lampis [IPEC 2017] and Froese [PhD thesis, 2018], it was shown by Kratsch, Masa\v{r}\'ik, Muzi, Pilipczuk, and Sorge [SODA 2021] that optimal discretization admits a fixed-parameter algorithm with running time $2^{\mathcal{O}(k^2 \log k)} \cdot n^{\mathcal{O}(1)}$, where $k$ is the solution size and $n = |R| + |B|$. In this paper we give an algorithm for optimal discretization that runs in time $\mathcal{O}(1.9602^n)$. We also study the related point separation problem that asks to separate all input points by axis-parallel lines. For this problem we obtain an algorithm with runtime $\mathcal{O}(1.8906^n)$. Our guarantees follow from structural observations about bichromatic and monochromatic point sets, and hold even if points are allowed to share coordinates. To our knowledge, these are the first improvements over the trivial $2^n$ bound for both problems.