Bichromatic 2-center of pairs of points (Q2261579)

Consider a set \(S\) of \(n\) pairs of points in the plane. In the pairs of points 1-center problem, one has to find a disk of minimum radius that encloses at least one point from each pair. Now assign a distinct color, either red or blue, to each point of every pair in \(S\). Denote the collection of red points by \(R\), and the collection of blue points by \(B\), and let \(C_R\) and \(C_B\) be their respective minimum enclosing disks. In the 2-center color assignment problem, one has to assign colors in such a way as to optimize the radii of \(C_R\) and \(C_B\). Specifically, in the \textsc{MinMax} variant of the problem, the maximum radius among \(C_R\) and \(C_B\) is to be minimized, while in the \textsc{MinSum} variant, the sum of their radii is to be minimized. The authors present algorithms for solving each of these variants of the 2-center color assignment problem, as well as for the pairs of points 1-center problem, in the case of the \(L_2\) (Euclidean) and \(L_\infty\) (maximum) metrics. In particular, the running times of the \textsc{MinMax} algorithms are shown to be \(O(n^3\log^2{n})\) and \(O(n)\), respectively, for the \(L_2\) and \(L_\infty\) metrics. The respective \textsc{MinSum} algorithms run in \(O(n^4\log^2{n})\) and \(O(n\log^2{n})\) time in the worst case. In addition, \((1+\epsilon)\)-approximation algorithms are given for \textsc{MinMax} and \textsc{MinSum} in the case of the \(L_2\) metric.