×

Improved algorithms for the bichromatic two-center problem for pairs of points. (English) Zbl 07445247

Summary: 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.

MSC:

68Uxx Computing methodologies and applications
68Qxx Theory of computing
68Wxx Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P. K.; Sharir, M., Planar geometric location problems, Algorithmica, 11, 185-195 (1994)
[2] Arkin, E. M.; Díaz-Báñez, J. M.; Hurtado, F.; Kumar, P.; Mitchell, J. S.B.; Palop, B.; Pérez-Lantero, P.; Saumell, M.; Silveira, R. I., Bichromatic 2-center of pairs of points, Comput. Geom. Theory Appl., 48, 94-107 (2015) · Zbl 1336.65015
[3] Chan, T. M., More planar two-center algorithms, Comput. Geom. Theory Appl., 13, 189-198 (1999) · Zbl 0948.68196
[4] Chazelle, B.; Matoušek, J., On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, 21, 579-597 (1996) · Zbl 0864.68040
[5] Cole, R., Slowing down sorting networks to obtain faster sorting algorithms, J. ACM, 34, 1, 200-208 (1987) · Zbl 1378.68037
[6] de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M., Computational Geometry — Algorithms and Applications (2008), Springer-Verlag: Springer-Verlag Berlin · Zbl 1140.68069
[7] Ding, H.; Xu, J., Solving the chromatic cone clustering problem via minimum spanning sphere, (Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP) (2011)), 773-784 · Zbl 1333.68292
[8] Dyer, M. E., On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM J. Comput., 15, 3, 725-738 (1986) · Zbl 0613.68044
[9] Eppstein, D., Faster construction of planar two-centers (1996), Dept. of Information and Computer Science, Univ. of California: Dept. of Information and Computer Science, Univ. of California Irvine, Technical Report 96-12
[10] Eppstein, D., Faster construction of planar two-centers, (Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1997)), 131-138 · Zbl 1321.68500
[11] Frederickson, G.; Johnson, D., The complexity of selection and ranking in \(X + Y\) and matrices with sorted columns, J. Comput. Syst. Sci., 24, 2, 197-208 (1982) · Zbl 0478.68062
[12] Frederickson, G.; Johnson, D., Generalized selection and ranking: sorted matrices, SIAM J. Comput., 13, 1, 14-30 (1984) · Zbl 0537.68059
[13] Hershberger, J., A faster algorithm for the two-center decision problem, Inf. Process. Lett., 1, 23-29 (1993) · Zbl 0776.68109
[14] Hershberger, J.; Suri, S., Finding tailored partitions, J. Algorithms, 3, 431-463 (1991) · Zbl 0726.68077
[15] Jaromczyk, J.; Kowaluk, M., An efficient algorithm for the Euclidean two-center problem, (Proceedings of the 10th Annual Symposium on Computational Geometry (SoCG) (1994)), 303-311
[16] Megiddo, N., Applying parallel computation algorithms in the design of serial algorithms, J. ACM, 30, 4, 852-865 (1983) · Zbl 0627.68034
[17] Megiddo, N., Linear-time algorithms for linear programming in \(R^3\) and related problems, SIAM J. Comput., 12, 4, 759-776 (1983) · Zbl 0521.68034
[18] Sharir, M., A near-linear algorithm for the planar 2-center problem, Discrete Comput. Geom., 125-134 (1997) · Zbl 0878.68131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.