Advertisement
Published in:
2019 | OriginalPaper | Chapter
Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points
Authors : Haitao Wang, Jie Xue
Published in: Algorithms and Data Structures
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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+\varepsilon )\)-approximate algorithm of \(O(n + (1/\varepsilon )^6 \log ^2 (1/\varepsilon ))\) time were known. In this paper, we propose a new exact algorithm of \(O(n^2\log ^2 n)\) time and a new \((1+\varepsilon )\)-approximate algorithm of \(O(n + (1/\varepsilon )^3 \log ^2 (1/\varepsilon ))\) time.