×

Planar bichromatic minimum spanning trees. (English) Zbl 1176.90597

Summary: Given a set \(S\) of \(n\) red and blue points in the plane, a planar bichromatic minimum spanning tree is the shortest possible spanning tree of \(S\), such that every edge connects a red and a blue point, and no two edges intersect. We show that computing this tree is NP-hard in general. For points in convex position, a cubic-time algorithm can be easily designed using dynamic programming. We adapt such an algorithm for the special case where the number of red points \((m)\) is much smaller than the number of blue points \((n)\), resulting in an \(O(nm^{2})\) time algorithm. For the general case, we present a factor \(O(\sqrt n)\) approximation algorithm that runs in \(O(n\log n\log \log n)\) time. Finally, we show that if the number of points in one color is bounded by a constant, the optimal tree can be computed in polynomial time.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abellanas, M.; Garcia-Lopez, J.; Hernández-Peñalver, G.; Noy, M.; Ramos, P. A., Bipartite embeddings of trees in the plane, Discr. Appl. Math., 93, 141-148 (1999) · Zbl 0929.05021
[2] Agarwal, P. K., Partitioning arrangements of lines, II: Applications, Discr. Comput. Geom., 5, 533-573 (1990) · Zbl 0709.68108
[3] Agarwal, P. K.; Edelsbrunner, H.; Schwarzkopf, O., Euclidean minimum spanning trees and bichromatic closest pairs, Discr. Comput. Geom., 6, 407-422 (1991) · Zbl 0753.68089
[4] Arora, S.; Chang, K. L., Approximation schemes for degree-restricted MST and red-blue separation problems, Algorithmica, 40, 189-210 (2004) · Zbl 1082.68125
[5] Atallah, M. J.; Chen, D. Z., On connecting red and blue rectilinear polygonal obstacles with nonintersecting monotone rectilinear paths, Int. J. Comput. Geom. Appl., 11, 373-400 (2001) · Zbl 1074.68628
[6] Baumgarten, H.; Jung, H.; Mehlhorn, K., Dynamic point location in general subdivisions, J. Algorithms, 17, 3, 342-380 (1994) · Zbl 0820.68122
[7] M.G. Borgelt, M. van Kreveld, M. Löffler, J. Luo, D. Merrick, R.I. Silveira, M. Vahedi, Planar bichromatic minimum spanning trees, Technical Report UU-CS-2007-044, Department of Information and Computing Sciences, Utrecht University, 2007; M.G. Borgelt, M. van Kreveld, M. Löffler, J. Luo, D. Merrick, R.I. Silveira, M. Vahedi, Planar bichromatic minimum spanning trees, Technical Report UU-CS-2007-044, Department of Information and Computing Sciences, Utrecht University, 2007 · Zbl 1176.90597
[8] Boissonnat, J.-D.; Czyzowicz, J.; Devillers, O.; Urrutia, J.; Yvinec, M., Computing largest circles separating two sets of segments, Int. J. Comput. Geom. Appl., 10, 41-53 (2000) · Zbl 1074.68631
[9] Bose, P.; Toussaint, G., Growing a tree from its branches, J. Algorithms, 19, 86-103 (1995) · Zbl 0836.68078
[10] Demaine, E. D.; Erickson, J.; Hurtado, F.; Iacono, J.; Langerman, S.; Meijer, H.; Overmars, M. H.; Whitesides, S., Separating point sets in polygonal environments, Int. J. Comput. Geom. Appl., 15, 403-420 (2005) · Zbl 1104.68116
[11] Everett, H.; Robert, J.-M.; van Kreveld, M. J., An optimal algorithm for the (⩽\(k)\)-levels, with applications to separation and transversal problems, Int. J. Comput. Geom. Appl., 6, 247-261 (1996) · Zbl 0859.68040
[12] M. Grantson, H. Meijer, D. Rappaport, Bi-chromatic minimum spanning trees, in: Proc. 21st Eur. Workshop on Comput. Geom. (EWCG05), 2005, pp. 199-202; M. Grantson, H. Meijer, D. Rappaport, Bi-chromatic minimum spanning trees, in: Proc. 21st Eur. Workshop on Comput. Geom. (EWCG05), 2005, pp. 199-202
[13] M. Hoffmann, C. Tòth, Pointed and colored binary encompassing trees, in: Proc. 21st Annu. ACM Sympos. Comput. Geom., 2005, pp. 81-90; M. Hoffmann, C. Tòth, Pointed and colored binary encompassing trees, in: Proc. 21st Annu. ACM Sympos. Comput. Geom., 2005, pp. 81-90 · Zbl 1387.68262
[14] Hurtado, F.; Kano, M.; Rappaport, D.; Tòth, C. D., Encompassing colored planar straight line graphs, Comput. Geom. Theory Appl., 39, 14-23 (2008) · Zbl 1124.05034
[15] Hurtado, F.; Noy, M.; Ramos, P. A.; Seara, C., Separating objects in the plane by wedges and strips, Discr. Appl. Math., 109, 109-138 (2001) · Zbl 0967.68160
[16] Kaneko, A.; Kano, M., Discrete geometry on red and blue points in the plane—a survey, (Discrete and Computational Geometry, The Goodman-Pollack Festschrift (2003), Springer-Verlag), 551-570 · Zbl 1079.52505
[17] Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 7, 48-50 (1956) · Zbl 0070.18404
[18] Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 329-343 (1982) · Zbl 0478.68043
[19] Mairson, H. G.; Stolfi, J., Reporting and counting intersections between two sets of line segments, (Earnshaw, R. A., Theoretical Foundations of Computer Graphics and CAD. Theoretical Foundations of Computer Graphics and CAD, NATO ASI, vol. F40 (1988), Springer-Verlag), 307-325
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.