CAREER: I/O-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.