Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points

Abstract

We consider a bichromatic two-center problem for pairs of points. Given a set $S$ of $n$ pairs of points in the plane, for every pair, we want to assign a red color to one point and a blue color to the other, in such a way that the value $\max \{r_1,r_2\}$ is minimized, where $r_1$ (resp., $r_2$) is the radius of the smallest enclosing disk of all red (resp., blue) points. Previously, an exact algorithm of $O(n^3{\log }^{2}n)$ time and a $(1+\epsilon )$-approximate algorithm of $O(n+(1/\epsilon {)}^6{\log }^2(1/\epsilon ))$ time were known. In this paper, we propose a new exact algorithm of $O(n^2{\log }^{2}n)$ time and a new $(1+\epsilon )$-approximate algorithm of $O(n+(1/\epsilon {)}^3{\log }^2(1/\epsilon ))$ time.

A preliminary version of this paper will appear in the Proceedings of the 16th Algorithms and Data Structures Symposium (WADS 2019)