Optimal distortion embedding of complete binary trees into lines

We study the problem of embedding an unweighted complete binary tree into a line with low distortion. Very recently, Mathieu and Papamanthou (2008) [9] showed that the inorder traversal of the complete binary tree of height h   gives a line embedding of distortion O(2h)O(2h), and conjectured that the current lower bound of Ω(2hh) increases to Ω(2h)Ω(2h), i.e., the upper bound of O(2h)O(2h) is best possible. In this paper, we disprove their conjecture by providing a line embedding of the complete binary tree of height h   with optimal distortion Θ(2hh).

► We study the line embedding problem of complete binary trees with low distortion. ► The lower bound on the distortion is Ω(2h/h)Ω(2h/h) for the tree of height h  . ► The previous upper bound on the distortion is O(2h)O(2h) for the tree of height h  . ► We provide a line embedding with optimal distortion Θ(2h/h)Θ(2h/h).