**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Fri, 28 Aug 2015 07:08:20 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*