New Themes in Data Structure Design

Data structures are the heart of many computer algorithms. Despite twenty-five years of intensive research in the area of data structures, new principles of data structure design an analysis are still being developed. This talk will focus on two such principles and their use in a simple and efficient solution to a classical problem of computational geometry. The principles are amortization, and analytical technique for averaging computational resources over a sequence of computer operations, and persistence, a property of data structures that allows old versions of a structure, as well as the current one, to be manipulated. The talk will describe persistent search trees, which give an efficient solution to the problem of planar point location, a special case of which is Knuth's post office problem.