Document Open Access Logo

The Diameter of Caterpillar Associahedra

Author Benjamin Aram Berendsohn

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.14.pdf
  • Filesize: 0.69 MB
  • 12 pages

Document Identifiers

Author Details

Benjamin Aram Berendsohn
  • Institut für Informatik, Freie Universität Berlin, Germany

Funding

Work supported by DFG grant KO 6140/1-1.

Acknowledgements

I would like to thank László Kozma for helpful discussions and suggestions.

Cite AsGet BibTex

Benjamin Aram Berendsohn. The Diameter of Caterpillar Associahedra. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.14

Abstract

The caterpillar associahedron 𝒜(G) is a polytope arising from the rotation graph of search trees on a caterpillar tree G, generalizing the rotation graph of binary search trees (BSTs) and thus the conventional associahedron. We show that the diameter of 𝒜(G) is Θ(n + m ⋅ (H+1)), where n is the number of vertices, m is the number of leaves, and H is the entropy of the leaf distribution of G. Our proofs reveal a strong connection between caterpillar associahedra and searching in BSTs. We prove the lower bound using Wilber’s first lower bound for dynamic BSTs, and the upper bound by reducing the problem to searching in static BSTs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Theory of computation → Data structures design and analysis
Keywords
  • Graph Associahedra
  • Binary Search Trees
  • Elimination Trees

Metrics

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

References

  1. Benjamin Aram Berendsohn and László Kozma. Splay trees on trees. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1875-1900, 2022. URL: https://doi.org/10.1137/1.9781611977073.75.
  2. Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, and Stefan Langerman. Competitive online search trees on trees. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1878-1891, 2020. URL: https://doi.org/10.1137/1.9781611975994.115.
  3. Jean Cardinal, Stefan Langerman, and Pablo Pérez-Lantero. On the diameter of tree associahedra. The Electronic Journal of Combinatorics, 2018. URL: https://doi.org/10.37236/7762.
  4. Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon. Bounds on the diameter of graph associahedra. Procedia Computer Science, 195:239-247, 2021. Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium. URL: https://doi.org/10.1016/j.procs.2021.11.030.
  5. Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon. Diameter estimates for graph associahedra. arXiv e-prints, 2021. URL: http://arxiv.org/abs/2106.16130.
  6. Michael Carr and Satyan L. Devadoss. Coxeter complexes and graph-associahedra. Topology and its Applications, 153:2155-2168, 2004. URL: https://doi.org/10.1016/j.topol.2005.08.010.
  7. Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the Strong Wilber 1 Bound for Binary Search Trees. In Jarosław Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:21, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.33.
  8. S. Cleary. Restricted rotation distance between binary trees. Inf. Process. Lett., 84:333-338, 2002. URL: https://doi.org/10.1016/S0020-0190(02)00315-0.
  9. Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătracommabelowscu. The geometry of binary search trees. In Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 496-505, 2009. URL: https://doi.org/10.1137/1.9781611973068.55.
  10. Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pătracommabelowscu. Dynamic optimality - almost. SIAM Journal on Computing, 37(1):240-251, 2007. URL: https://doi.org/10.1137/S0097539705447347.
  11. D. E. Knuth. Optimum binary search trees. Acta Informatica, 1(1):14-25, March 1971. URL: https://doi.org/10.1007/BF00264289.
  12. Jussi Kujala and Tapio Elomaa. The cost of offline binary search tree algorithms and the complexity of the request sequence. Theoretical Computer Science, 393(1):231-239, 2008. URL: https://doi.org/10.1016/j.tcs.2007.12.015.
  13. Victor Lecomte and Omri Weinstein. Settling the relationship between wilber’s bounds for dynamic optimality. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:21, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.68.
  14. J.M. Lucas. Canonical forms for competitive binary search tree algorithms. Technical report DCS-TR-250, Department of Computer Science, Hill Center for the Mathematical Sciences, Busch Campus, Rutgers University, New Brunswick, New Jersey 08903, 1988. Google Scholar
  15. Thibault Manneville and Vincent Pilaud. Graph properties of graph associahedra. Séminaire Lotharingien de Combinatoire, 73, 2015. URL: https://www.mat.univie.ac.at/~slc/wpapers/s73mannpil.html.
  16. Kurt Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5(4):287-295, December 1975. URL: https://doi.org/10.1007/BF00264563.
  17. J. Ian Munro. On the competitiveness of linear search. In Mike S. Paterson, editor, Algorithms - ESA 2000, pages 338-345, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-45253-2_31.
  18. L. Pournin. The asymptotic diameter of cyclohedra. Israel Journal of Mathematics, 219:609-635, 2014. URL: https://doi.org/10.1007/s11856-017-1492-0.
  19. Lionel Pournin. The diameter of associahedra. Advances in Mathematics, 259:13-42, 2014. URL: https://doi.org/10.1016/j.aim.2014.02.035.
  20. D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM, 32:652-686, 1985. URL: https://doi.org/10.1145/3828.3835.
  21. Daniel D Sleator, Robert E Tarjan, and William P Thurston. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society, 1(3):647-681, 1988. URL: https://doi.org/10.1090/S0894-0347-1988-0928904-4.
  22. Robert Wilber. Lower bounds for accessing binary search trees with rotations. SIAM journal on Computing, 18(1):56-67, 1989. URL: https://doi.org/10.1137/0218004.
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