Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Planar Bichromatic Bottleneck Spanning Trees

Authors A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, Joseph S. B. Mitchell

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.1.pdf
  • Filesize: 0.93 MB
  • 16 pages

Document Identifiers

Author Details

A. Karim Abu-Affash
  • Software Engineering Department, Shamoon College of Engineering, Beer-Sheva, Israel
Sujoy Bhore
  • Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel
Paz Carmi
  • Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel
Joseph S. B. Mitchell
  • Department of Applied Mathematics and Statistics, Stony Brook University, NY, USA

Funding

This work was partially supported by Grant 2016116 from the United States - Israel Binational Science Foundation. Work by J. Mitchell was partially supported by NSF (CCF-1526406, CCF-2007275).

Cite AsGet BibTex

A. Karim Abu-Affash, Sujoy Bhore, Paz Carmi, and Joseph S. B. Mitchell. Planar Bichromatic Bottleneck Spanning Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.1

Abstract

Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a geometric spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Our main contribution is a polynomial-time (8√2)-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√2 λ.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Approximation Algorithms
  • Bottleneck Spanning Tree
  • NP-Hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Abellanas, J. Garcia-Lopez, G. Hernández-Peñalver, M. Noy, and P. A. Ramos. Bipartite embeddings of trees in the plane. Discr. Appl. Math., 93(2-3):141-148, 1999. Google Scholar
  2. A. K. Abu-Affash, A. Biniaz, P. Carmi, A. Maheshwari, and M. Smid. Approximating the bottleneck plane perfect matching of a point set. Comput. Geom., 48(9):718-731, 2015. Google Scholar
  3. A. K. Abu-Affash, P. Carmi, M. J. Katz, and Y. Trabelsi. Bottleneck non-crossing matching in the plane. Comput. Geom., 47(3):447-457, 2014. Google Scholar
  4. P. K. Agarwal. Partitioning arrangements of lines II: Applications. Discr. Comput. Geom., 5(1):533-573, 1990. Google Scholar
  5. P. K. Agarwal, H. Edelsbrunner, and O. Schwarzkopf. Euclidean minimum spanning trees and bichromatic closest pairs. Discr. Comput. Geom., 6(1):407-422, 1991. Google Scholar
  6. O. Aichholzer, S. Cabello, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood. Edge-removal and non-crossing configurations in geometric graphs. In EuroCG, pages 119-122, 2008. Google Scholar
  7. N. Alon, S. Rajagopalan, and S. Suri. Long non-crossing configurations in the plane. In SoCG, pages 257-263, 1993. Google Scholar
  8. G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, and P. Taslakian. Matching points with things. In LATIN, volume 6034 of LNCS, pages 456-467, 2010. Google Scholar
  9. S. Arora and K. L. Chang. Approximation schemes for degree-restricted MST and red–blue separation problems. Algorithmica, 40(3):189-210, 2004. Google Scholar
  10. M. J. Atallah and D. Z. Chen. On connecting red and blue rectilinear polygonal obstacles with nonintersecting monotone rectilinear paths. Int. J. Comput. Geom. Appl., 11(4):373-400, 2001. Google Scholar
  11. A. Biniaz, P. Bose, K. Crosbie, J.-L. De Carufel, D. Eppstein, A. Maheshwari, and M. H. M. Smid. Maximum plane trees in multipartite geometric graphs. Algorithmica, 81(4):1512-1534, 2019. Google Scholar
  12. A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. H. M. Smid. Spanning trees in multipartite geometric graphs. Algorithmica, 80(11):3177-3191, 2018. Google Scholar
  13. A. Biniaz, A. Maheshwari, and M. Smid. Bottleneck bichromatic plane matching of points. In CCCG, 2014. Google Scholar
  14. J.-D. Boissonnat, J. Czyzowicz, O. Devillers, J. Urrutia, and M. Yvinec. Computing largest circles separating two sets of segments. Int. J. Comput. Geom. Appl., 10(1):41-53, 2000. Google Scholar
  15. M. G. Borgelt, M. Van Kreveld, M. Löffler, J. Luo, D. Merrick, R. I. Silveira, and M. Vahedi. Planar bichromatic minimum spanning trees. J. Discrete Algorithms, 7(4):469-478, 2009. Google Scholar
  16. H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990. URL: https://doi.org/10.1007/BF02122694.
  17. E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, M. H. Overmars, and S. Whitesides. Separating point sets in polygonal environments. Int. J. Comput. Geom. Appl., 15(4):403-419, 2005. Google Scholar
  18. A. Dumitrescu and R. Kaye. Matching colored points in the plane: some new results. Comput. Geom., 19(1):69-85, 2001. Google Scholar
  19. A. Dumitrescu and J. Pach. Partitioning colored point sets into monochromatic parts. Int. J. Comput. Geom. Appl., 12(05):401-412, 2002. Google Scholar
  20. H. Everett, J.-M. Robert, and M. J. van Kreveld. An optimal algorithm for the (less= k)-levels, with applications to separation and transversal problems. Int. J. Comput. Geom. Appl., 6(3):247-261, 1996. Google Scholar
  21. A. Kaneko and M. Kano. Discrete geometry on red and blue points in the plane - a survey. Discr. Comput. Geom., 25:551-570, 2003. Google Scholar
  22. D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982. Google Scholar
  23. H. G. Mairson and J. Stolfi. Reporting and counting intersections between two sets of line segments. In Theoretical Foundations of Computer Graphics and CAD, volume 40 of NATO ASI Series, pages 307-325, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact