Levcopoulos, C., Lingas, A., and Sack, J.-R. (1987). Nearly Optimal Heuristics for Binary Search Trees with Geometric Generalizations. Technical Report LiTH-IDA-R-87-08, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc of ICALP'87, Karlsruhe, July 1987. (bibtex),
Abstract: New results concerning optimal binary search trees with zero key access probabilities (with applications eg. in code theory and in point location) are derived. It is shown that for an arbitrarily small positive constant epsilon, there exists a linear-time heuristic for such search trees, producing solutions within the factor of 1+epsilon from the optimum. Also, by using an interesting amortization argument, we give a simple and practical, linear-time implementation of a known greedy heuristic for such trees. The above results are obtained in a more general setting, namely in the context of minimum length triangulations of so-called semi-circular polygons. They are carried over to binary search trees by proving a duality between minimum weight partitions of infinitely-flat semi-circular polygons into m-gons and optimal (m-1)-way search trees. This duality helps also to obtain better heuristics for minimum length partitions of polygons using known algorithms for optimal search trees.
CS Dept TR Overview