US-Belgium Cooperative Research: Retroactive Data Structures

Polytechnic University Of New York, Brooklyn NY

Investigators

Abstract

0334653 Iacono This three-year award supports US-Belgium cooperative research in retroactive data structures involving John Iacono of the Polytechnic University of New York and Erik Demaine of the Massachusetts Institute of Technology and Stefan Langerman at the National Fund for Scientific Research in Belgium. The objectives of the project are to develop retroactive analogs of both fundamental and application-driven data structures to demonstrate how retroactive data structures can solve the dynamic planar point location problem, an open problem in computational geometry. The paradigm of retroactive data structures could be incorporated into any graduate algorithms class for broader dissemination. The collaboration will develop the model of retroactive data structures, explore possible variants on the model, seek to prove general results and transformations involving retroactive data structures, analyze specific data structures for which efficient retroactive structures can be developed, and explore the impact that retroactive data structures can have outsie the data-structures community.