This project is a continuation of a multi-year effort to discover and understand efficient data structures, combinatorial algorithms, and the relationships between the two. The emphasis is placed on studying problems that are fundamental, longstanding, and/or of significant practical importance. Sought are not only specific algorithmic results, but also general principles of design and analysis. In particular, the goals of the project include: (1) to devise specific algorithms and data structures that result in more efficient solutions of important combinatorial problems; (2) to study the worst-case and typical-case performance of new and older methods, to allow prediction of the best method for a given situation; (3) to develop general tools and principles for design and analysis, and apply these tools and principles systematically in the construction of new algorithms and data structures. Asymptotic efficiency is not the only goal; methods are sought that display simplicity and even elegance in addition to efficiency. Success is achieved when a method is found that is both theoretically efficient and usable in practice. The objective is not only to devise new methods, but to gain greater insights into old ones, so that all solutions can be stripped down to their essence, achieving both greater efficiency and greater simplicity.***
