Bichromatic 2-center of pairs of points (Q2261579)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bichromatic 2-center of pairs of points |
scientific article |
Statements
Bichromatic 2-center of pairs of points (English)
0 references
6 March 2015
0 references
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.
0 references
pairs of points
0 references
color assignment
0 references
minimum enclosing disk
0 references
2-center problem
0 references
pairs of points 1-center problem
0 references
2-center color assignment problem
0 references
algorithm
0 references
0 references