Extensions of the Maximum Bichromatic Separating Rectangle Problem

In this paper, we study two extensions of the maximum bichromatic separating rectangle (MBSR) problem introduced in \cite{Armaselu-CCCG, Armaselu-arXiv}. One of the extensions, introduced in \cite{Armaselu-FWCG}, is called $\mathit{\text{MBSR}}\mathit{\text{with}}\mathit{\text{outliers}}$ or MBSR-O, and is a more general version of the MBSR problem in which the optimal rectangle is allowed to contain up to $k$ outliers, where $k$ is given as part of the input. For MBSR-O, we improve the previous known running time bounds of $O(k^{7}m\log m+n)$ to $O(k^3 m + m \log m + n)$. The other extension is called $\mathit{\text{MBSR}}\mathit{\text{among}}\mathit{\text{circles}}$ or MBSR-C and asks for the largest axis-aligned rectangle separating red points from blue unit circles. For MBSR-C, we provide an algorithm that runs in $O(m^2

• n)$ time.