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.

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