@techreport{R-87-08,
TITLE = {Nearly Optimal Heuristics for Binary Search Trees with Geometric Generalizations},
AUTHOR = {Christos Levcopoulos and Andrzej Lingas and J{\"o}rg-R. Sack },
YEAR = {1987},
NUMBER = {R-87-08},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-87-08+abstr},
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.},
IDANR = {LiTH-IDA-R-87-08},
NOTE = {Also in Proc of ICALP'87, Karlsruhe, July 1987}