CAREER: I/O-Efficient Geometric Algorithms

职业：I/O 高效的几何算法

• 批准号: 9984099
• 负责人: Lars Arge
• 金额: $ 24.14万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-04-15 至 2005-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9984099&HistoricalAwards=false
• 关键词: CAREER; Efficient; Geometric; Algorithms

Geometric problems arise in numerous application areas such as computergraphics, geographic information systems (GISs), spatial database systems,computer aided design, robotics, physics, and meteorology. The field ofcomputational geometry is largely motivated by this fact. In the lasttwenty years impressive progress has been made in the field. However, eventhough computational geometry is now a rich and mature discipline, thealgorithms and techniques developed in the field have had too littlepractical impact in application areas. One reason for this disparity isthat the goal of traditional algorithms design has been to optimizeinternal memory computation time (CPU efficiency). However, many geometricapplications frequently involve massive amounts of data. Often the datasetsare too large to fit in main memory and must reside on disk, andcommunication between internal and external memory, and not actualcomputation time, is the bottleneck in the computation. This effect arisesfrom the huge difference in access time of fast internal memory and slowerexternal memory such as disks.This project contains a challenging career development plan focusing onInput/Output-efficient (or I/O-efficient) computational geometryalgorithms. Key components of the plan are the rich and importantpossibilities for interplay between theory and practice in the area, aswell as the exciting possibilities the area gives for interdisciplinarycollaboration and for bringing research into the classroom. Theoreticalwork will concentrate on developing I/O-efficient algorithms and datastructures for geometric problems. A main goal is to develop simple andpractically efficient algorithms, and in order to do so, theoreticallydeveloped algorithms will be implemented and tested using real-lifedata. In this work, focus will be on problems with direct practicalapplications and on collaboration with researchers in other areas ofcomputer science, as well as with researchers in application areas. A keyobjective of the career plan is for the PI to obtain a certain level ofexpertise in select application areas and to build up a ``track record'' inthese areas. Curriculum development is also an integrated part of the plan.Work will be done on incorporating I/O-efficiency into the curriculum ofundergraduate and graduate algorithms classes, and new classes, as well aseducational material, will be developed.Altogether, the outcome of the project will not only be theoreticaladvances in I/O-efficient geometric algorithms, but also the developmentand implementation of practical efficient algorithms as well as curricularinnovations. At the same time the project will build a strong foundationfor the PIs continued work in research and education.

几何问题出现在许多应用领域，如计算机图形学，地理信息系统（GIS），空间数据库系统，计算机辅助设计，机器人，物理学和气象学。计算几何领域的发展很大程度上是由这一事实推动的。在过去的二十年里，这一领域取得了令人瞩目的进展。然而，尽管计算几何现在是一门丰富而成熟的学科，但该领域开发的算法和技术在应用领域的实际影响太小。造成这种差异的一个原因是，传统算法设计的目标是优化内存计算时间（CPU效率）。然而，许多几何应用经常涉及大量数据。通常情况下，内存太大，无法放入主存，必须驻留在磁盘上，而内部和外部存储器之间的通信，而不是实际的计算时间，是计算中的瓶颈。 这个项目包含一个具有挑战性的职业发展计划，重点是输入/输出效率（或I/O效率）的计算几何算法。该计划的关键组成部分是该地区理论与实践之间相互作用的丰富而重要的可能性，以及该地区为跨学科合作和将研究带入课堂提供的令人兴奋的可能性。理论工作将集中在开发I/O高效的算法和数据结构的几何问题。一个主要的目标是开发简单和实际有效的算法，为了做到这一点，理论上开发的算法将使用现实生活中的数据来实现和测试。在这项工作中，重点将放在直接的实际应用问题上，并与计算机科学其他领域的研究人员以及应用领域的研究人员合作。职业规划的一个主要目标是PI在选定的应用领域获得一定程度的专业知识，并在这些领域建立“跟踪记录”。课程开发也是该计划的一个组成部分。将把I/O效率纳入研究生和研究生算法课程，并将开发新课程和教育材料。总之，该项目的成果不仅是I/O效率几何算法的理论进步，而且还开发和实现了实用高效的算法以及实用的创新。与此同时，该项目将为PI继续开展研究和教育工作奠定坚实的基础。