US-Belgium Cooperative Research: Retroactive Data Structures

美国-比利时合作研究：追溯数据结构

• 批准号: 0334653
• 负责人: John Iacono
• 金额: --
• 依托单位: Polytechnic University of New York
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-10-01 至 2008-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0334653&HistoricalAwards=false
• 关键词: US; Belgium; Cooperative; Research; Retroactive

0334653IaconoThis 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.

这个为期三年的奖项支持美国和比利时在追溯数据结构方面的合作研究，参与者包括纽约理工大学的John Iacono、麻省理工学院的Erik Demaine和比利时国家科学研究基金的Stefan Langerman。该项目的目标是开发基础数据结构和应用驱动数据结构的回溯模拟，以演示回溯数据结构如何解决动态平面点定位问题，这是计算几何中的一个开放问题。追溯数据结构的范例可以被纳入任何研究生算法课程，以进行更广泛的传播。该合作将开发溯及性数据结构模型，探索该模型的可能变体，寻求证明涉及溯及性数据结构的一般结果和转换，分析可以开发有效溯及性结构的特定数据结构，并探索溯及性数据结构在数据结构社区之外的影响。