CAREER: I/O-Efficient Geometric Algorithms

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

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.