Paper by Erik D. Demaine

Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pǎtraşcu, “The Geometry of Binary Search Trees”, in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, New York, January 4–6, 2009, pages 496–505.

We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:
  1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.
  2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].
  3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.

The paper is 10 pages.

The paper is available in PostScript (1031k), gzipped PostScript (161k), and PDF (492k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated September 3, 2017 by Erik Demaine.