CAREER: I/O-Efficient Geometric Algorithms

Duke University, Durham NC

Investigators

Abstract

Geometric problems arise in numerous application areas such as computer graphics, geographic information systems (GISs), spatial database systems, computer aided design, robotics, physics, and meteorology. The field of computational geometry is largely motivated by this fact. In the last twenty years impressive progress has been made in the field. However, even though computational geometry is now a rich and mature discipline, the algorithms and techniques developed in the field have had too little practical impact in application areas. One reason for this disparity is that the goal of traditional algorithms design has been to optimize internal memory computation time (CPU efficiency). However, many geometric applications frequently involve massive amounts of data. Often the datasets are too large to fit in main memory and must reside on disk, and communication between internal and external memory, and not actual computation time, is the bottleneck in the computation. This effect arises from the huge difference in access time of fast internal memory and slower external memory such as disks. This project contains a challenging career development plan focusing on Input/Output-efficient (or I/O-efficient) computational geometry algorithms. Key components of the plan are the rich and important possibilities for interplay between theory and practice in the area, as well as the exciting possibilities the area gives for interdisciplinary collaboration and for bringing research into the classroom. Theoretical work will concentrate on developing I/O-efficient algorithms and data structures for geometric problems. A main goal is to develop simple and practically efficient algorithms, and in order to do so, theoretically developed algorithms will be implemented and tested using real-life data. In this work, focus will be on problems with direct practical applications and on collaboration with researchers in other areas of computer science, as well as with researchers in application areas. A key objective of the career plan is for the PI to obtain a certain level of expertise in select application areas and to build up a ``track record'' in these areas. Curriculum development is also an integrated part of the plan. Work will be done on incorporating I/O-efficiency into the curriculum of undergraduate and graduate algorithms classes, and new classes, as well as educational material, will be developed. Altogether, the outcome of the project will not only be theoretical advances in I/O-efficient geometric algorithms, but also the development and implementation of practical efficient algorithms as well as curricular innovations. At the same time the project will build a strong foundation for the PIs continued work in research and education.