Document Open Access Logo

Improved Bounds for Covering Paths and Trees in the Plane

Author Ahmad Biniaz

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.19.pdf
  • Filesize: 0.92 MB
  • 15 pages

Document Identifiers

Author Details

Ahmad Biniaz
  • School of Computer Science, University of Windsor, Canada

Funding

Research supported by NSERC.

Cite AsGet BibTex

Ahmad Biniaz. Improved Bounds for Covering Paths and Trees in the Plane. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.19

Abstract

A covering path for a planar point set is a path drawn in the plane with straight-line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let π(n) be the minimum number such that every set of n points in the plane can be covered by a noncrossing path with at most π(n) edges. Let τ(n) be the analogous number for noncrossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: 5n/9 - O(1) < π(n) < (1-1/601080391)n, and 9n/17 - O(1) < τ(n) ⩽ ⌊5n/6⌋. We report the following improved upper bounds: π(n) ⩽ (1-1/22)n, and τ(n) ⩽ ⌈4n/5⌉. In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let ρ(k) be the minimum number such that every k-colored point set in the plane admits a perfect rainbow polygon of size ρ(k). Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that 20k/19 - O(1) < ρ(k) < 10k/7 + O(1). We report the improved upper bound of ρ(k) < 7k/5 + O(1). To obtain the improved bounds we present simple O(nlog n)-time algorithms that achieve paths, trees, and polygons with our desired number of edges.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Discrete mathematics
Keywords
  • planar point sets
  • covering paths
  • covering trees
  • rainbow polygons

Metrics

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

Related Versions

References

  1. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. SIAM Journal on Computing, 29(3):697-711, 1999. Also in SODA'97. Google Scholar
  2. Oswin Aichholzer, Sergio Cabello, Ruy Fabila Monroy, David Flores-Peñaloza, Thomas Hackl, Clemens Huemer, Ferran Hurtado, and David R. Wood. Edge-removal and non-crossing configurations in geometric graphs. Discrete Mathematics & Theoretical Computer Science, 12(1):75-86, 2010. Google Scholar
  3. Oswin Aichholzer, Frank Duque, Ruy Fabila Monroy, Oscar E. García-Quintero, and Carlos Hidalgo-Toscano. An ongoing project to improve the rectilinear and the pseudolinear crossing constants. Journal of Graph Algorithms and Applications, 24(3):421-432, 2020. Google Scholar
  4. Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, and Tae-Cheon Yang. On the maximum scatter traveling salesperson problem. SIAM Journal on Computing, 29(2):515-544, 1999. Also in SODA'97. Google Scholar
  5. Esther M. Arkin, Joseph S. B. Mitchell, and Christine D. Piatko. Minimum-link watchman tours. Information Processing Letters, 86(4):203-207, 2003. Google Scholar
  6. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998. Google Scholar
  7. Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, and Pavel Valtr. Traversing a set of points with a minimum number of turns. Discrete & Computational Geomometry, 41(4):513-532, 2009. Also in SoCG'07. Google Scholar
  8. Ahmad Biniaz. Euclidean bottleneck bounded-degree spanning tree ratios. Discrete & Computational Geometry, 67(1):311-327, 2022. Also in SODA'20. Google Scholar
  9. Jakub Cerný, Zdenek Dvorák, Vít Jelínek, and Jan Kára. Noncrossing Hamiltonian paths in geometric graphs. Discrete Applied Mathematics, 155(9):1096-1105, 2007. Google Scholar
  10. Timothy M. Chan. Euclidean bounded-degree spanning tree ratios. Discrete & Computational Geometry, 32(2):177-194, 2004. Also in SoCG 2003. Google Scholar
  11. Jianer Chen, Qin Huang, Iyad Kanj, and Ge Xia. Near-optimal algorithms for point-line covering problems. CoRR, abs/2012.02363, 2020. Google Scholar
  12. Michael J. Collins. Covering a set of points with a minimum number of turns. International Journal of Computational Geometry & Applications, 14(1-2):105-114, 2004. Google Scholar
  13. Éva Czabarka, Ondrej Sýkora, László A. Székely, and Imrich Vrto. Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method. Random Structures & Algorithms, 33(4):480-496, 2008. Google Scholar
  14. Erik D. Demaine and Joseph O'Rourke. Open problems from CCCG 2010. In Proceedings of the 22nd Canadian Conference on Computational Geometry, 2011. Google Scholar
  15. Adrian Dumitrescu, Dániel Gerbner, Balázs Keszegh, and Csaba D. Tóth. Covering paths for planar point sets. Discrete & Computational Geometry, 51(2):462-484, 2014. Google Scholar
  16. P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  17. Sándor P. Fekete and Henk Meijer. On minimum stars and maximum matchings. Discrete & Computational Geometry, 23(3):389-407, 2000. Also in SoCG 1999. Google Scholar
  18. Sándor P. Fekete and Gerhard J. Woeginger. Angle-restricted tours in the plane. Computational Geometry: Theory and Applications, 8:195-218, 1997. Google Scholar
  19. David Flores-Peñaloza, Mikio Kano, Leonardo Martínez-Sandoval, David Orden, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber. Rainbow polygons for colored point sets in the plane. Discrete Mathematics, 344(7):112406, 2021. Google Scholar
  20. Radoslav Fulek, Balázs Keszegh, Filip Morić, and Igor Uljarević. On polygons excluding point sets. Graphs and Combinatorics, 29(6):1741-1753, 2013. Google Scholar
  21. Magdalene Grantson and Christos Levcopoulos. Covering a set of points with a minimum number of lines. In Proceedings of the 6th International Conference on Algorithms and Complexity (CIAC), pages 6-17, 2006. Google Scholar
  22. Frank Harary and Anthony Hill. On the number of crossings in a complete graph. Proceedings of the Edinburgh Mathematical Society, 13:333-338, 1963. Google Scholar
  23. Alexandr O. Ivanov and Alexey A. Tuzhilin. The Steiner ratio Gilbert-Pollak conjecture is still open: Clarification statement. Algorithmica, 62(1-2):630-632, 2012. Google Scholar
  24. Minghui Jiang. On covering points with minimum turns. International Journal of Computational Geometry & Applications, 25(1):1-10, 2015. Google Scholar
  25. Balázs Keszegh. Covering paths and trees for planar grids. Geombinatorics Quarterly, 24, 2014. Google Scholar
  26. Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. Also in ESA'02. Google Scholar
  27. Samuel Loyd. Cyclopedia of 5000 Puzzles, Tricks & Conundrums. The Lamb Publishing Company, 1914. Google Scholar
  28. János Pach, Natan Rubin, and Gábor Tardos. Planar point sets determine many pairwise crossing segments. Advances in Mathematics, 386:107779, 2021. Also in STOC'19. Google Scholar
  29. Christos H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science, 4(3):237-244, 1977. Google Scholar
  30. Clifford Stein and David P. Wagner. Approximation algorithms for the minimum bends traveling salesman problem. In Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 406-422, 2001. 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