Document Open Access Logo

Long Plane Trees

Authors Sergio Cabello , Michael Hoffmann , Katharina Klost, Wolfgang Mulzer , Josef Tkadlec

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.23.pdf
  • Filesize: 1.17 MB
  • 17 pages

Document Identifiers

Author Details

Sergio Cabello
  • Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
  • Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
Michael Hoffmann
  • Department of Computer Science, ETH Zürich, Switzerland
Katharina Klost
  • Institut für Informatik, Freie Universität Berlin, Germany
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, Germany
Josef Tkadlec
  • Department of Mathematics, Harvard University, Cambridge, MA, USA

Funding

  • Cabello, Sergio: Supported by the Slovenian Research Agency (P1-0297, J1-9109, J1-8130, J1-8155, J1-1693, J1-2452).
  • Hoffmann, Michael: Supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681.
  • Mulzer, Wolfgang: Supported in part by ERC StG 757609.

Cite As Get BibTex

Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec. Long Plane Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.23

Abstract

In the longest plane spanning tree problem, we are given a finite planar point set 𝒫, and our task is to find a plane (i.e., noncrossing) spanning tree T_OPT for 𝒫 with maximum total Euclidean edge length |T_OPT|. Despite more than two decades of research, it remains open if this problem is NP-hard. Thus, previous efforts have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates |T_OPT|. The approximate trees in these algorithms all have small unweighted diameter, typically three or four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms.
We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree T_ALG with diameter at most four and |T_ALG| ≥ 0.546 ⋅ |T_OPT|. This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter d ≥ 3, we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most d (compared to a longest plane tree without constraints).

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Computational geometry
  • Mathematics of computing → Trees
Keywords
  • geometric network design
  • spanning trees
  • plane straight-line graphs
  • approximation algorithms

Metrics

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

Related Versions

References

  1. Noga Alon, Sridhar Rajagopalan, and Subhash Suri. Long non-crossing configurations in the plane. Fundam. Inform., 22(4):385-394, 1995. URL: https://doi.org/10.3233/FI-1995-2245.
  2. Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila-Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, and Perouz Taslakian. Matching points with things. In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, volume 6034, pages 456-467, 2010. URL: https://doi.org/10.1007/978-3-642-12200-2_40.
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753-782, 1998. URL: https://doi.org/10.1145/290179.290180.
  4. Sanjeev Arora and Kevin L. Chang. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica, 40(3):189-210, 2004. URL: https://doi.org/10.1007/s00453-004-1103-4.
  5. Alexander I. Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, and Russell Woodroofe. The geometric maximum traveling salesman problem. J. ACM, 50(5):641-664, 2003. URL: https://doi.org/10.1145/876638.876640.
  6. Ahmad Biniaz. Euclidean bottleneck bounded-degree spanning tree ratios. In Proc. 31st Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 826-836, 2020. URL: https://doi.org/10.1137/1.9781611975994.50.
  7. Ahmad Biniaz. Improved approximation ratios for two Euclidean maximum spanning tree problems, 2020. URL: http://arxiv.org/abs/2010.03870.
  8. Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, and Michiel Smid. Maximum plane trees in multipartite geometric graphs. Algorithmica, 81(4):1512-1534, 2019. URL: https://doi.org/10.1007/s00453-018-0482-x.
  9. Johannes Blömer. Computing sums of radicals in polynomial time. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pages 670-677, 1991. URL: https://doi.org/10.1109/SFCS.1991.185434.
  10. Sergio Cabello, Aruni Choudhary, Michael Hoffmann, Katharina Klost, Meghana M Reddy, Wolfgang Mulzer, Felix Schröder, and Josef Tkadlec. A better approximation for longest noncrossing spanning trees. In 36th European Workshop on Computational Geometry (EuroCG), 2020. Google Scholar
  11. Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec. Long plane trees. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.00445.
  12. Timothy M. Chan. Euclidean bounded-degree spanning tree ratios. Discrete Comput. Geom., 32(2):177-194, 2004. URL: http://www.springerlink.com/index/10.1007/s00454-004-1117-3.
  13. Francis Y. L. Chin, Jianbo Qian, and Cao An Wang. Progress on maximum weight triangulation. In Proc. 10th Annu. Int. Conf. Computing and Combinatorics (COCOON), pages 53-61, 2004. URL: https://doi.org/10.1007/978-3-540-27798-9_8.
  14. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 3rd edition, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  15. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry. Algorithms and applications. Springer-Verlag, Berlin, third edition, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
  16. Adrian Dumitrescu and Csaba D. Tóth. Long non-crossing configurations in the plane. Discrete Comput. Geom., 44(4):727-752, 2010. URL: https://doi.org/10.1007/s00454-010-9277-9.
  17. Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1):1-28, 2001. URL: https://doi.org/10.1007/s00453-001-0016-8.
  18. David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461. North Holland / Elsevier, 2000. URL: https://doi.org/10.1016/b978-044482537-7/50010-3.
  19. Andrea Francke and Michael Hoffmann. The Euclidean degree-4 minimum spanning tree problem is NP-hard. In Proceedings of the 25th ACM Symposium on Computational Geometry, pages 179-188. ACM, 2009. URL: https://doi.org/10.1145/1542362.1542399.
  20. P. D. Gilbert. New results in planar triangulations. Technical Report R-850, Univ. Illinois Coordinated Science Lab, 1979. Google Scholar
  21. Sariel Har-Peled. Geometric approximation algorithms, volume 173 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2011. URL: https://doi.org/10.1090/surv/173.
  22. Gheza Tom Klincsek. Minimal triangulations of polygonal domains. Ann. Discrete Math., 9:121-123, 1980. Google Scholar
  23. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999. URL: https://doi.org/10.1137/S0097539796309764.
  24. Joseph S. B. Mitchell. Shortest paths and networks. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 607-641. Chapman and Hall/CRC, 2nd edition, 2004. URL: https://doi.org/10.1201/9781420035315.ch27.
  25. Joseph S. B. Mitchell and Wolfgang Mulzer. Proximity algorithms. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 32, pages 849-874. CRC Press, Boca Raton, 3rd edition, 2017. URL: https://doi.org/10.1201/9781315119601.
  26. Wolfgang Mulzer. Minimum dilation triangulations for the regular n-gon. Master’s thesis, Freie Universität Berlin, Germany, 2004. Google Scholar
  27. Wolfgang Mulzer and Johannes Obenaus. The tree stabbing number is not monotone. In Proceedings of the 36th European Workshop on Computational Geometry (EWCG), pages 78:1-78:8, 2020. Google Scholar
  28. Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is NP-hard. J. ACM, 55(2):11:1-11:29, 2008. URL: https://doi.org/10.1145/1346330.1346336.
  29. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, Cambridge, 2007. URL: https://doi.org/10.1017/CBO9780511546884.
  30. Christos H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci., 4(3):237-244, 1977. URL: https://doi.org/10.1016/0304-3975(77)90012-3.
  31. Christos H. Papadimitriou and Umesh V. Vazirani. On two geometric problems related to the traveling salesman problem. J. Algorithms, 5(2):231-246, 1984. URL: https://doi.org/10.1016/0196-6774(84)90029-4.
  32. Jan Remy and Angelika Steger. A quasi-polynomial time approximation scheme for minimum weight triangulation. J. ACM, 56(3):15:1-15:47, 2009. URL: https://doi.org/10.1145/1516512.1516517.
  33. Emo Welzl. On spanning trees with low crossing numbers. In Data structures and efficient algorithms, volume 594 of Lecture Notes in Comput. Sci., pages 233-249. Springer, Berlin, 1992. URL: https://doi.org/10.1007/3-540-55488-2_30.
  34. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: https://doi.org/10.1017/CBO9780511921735.
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 About DROPS Imprint Privacy Contact