2026-07-29T23:24:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16174 2024-03-06T10:57:04Z ddc:004 open_access

The Diameter of Caterpillar Associahedra Berendsohn, Benjamin Aram Graph Associahedra Binary Search Trees Elimination Trees 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Aram Berendsohn 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.14 urn:nbn:de:0030-drops-161743 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode