Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Improved Algorithms for the Bichromatic Two-Center Problem for Pairs of Points
verfasst von : Haitao Wang, Jie Xue
Erschienen in: Algorithms and Data Structures
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.