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

05/01/2019

∙

by   Haitao Wang, et al.

∙

0

∙

share

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^3log^2 n) time and a (1+ε)-approximate algorithm of O(n + (1/ε)^6 log^2 (1/ε)) time were known. In this paper, we propose a new exact algorithm of O(n^2log^2 n) time and a new (1+ε)-approximate algorithm of O(n + (1/ε)^3 log^2 (1/ε)) time.