CAREER: Approximation Algorithms for Geometric Computing

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

0132901 Har-Peled, Sariel U of Ill, Urbana-Champaign Computational geometry is the branch of theoretical computer science devoted to the design, analysis, and implementation of geometric algorithms and data structures. Computational geometry has deep roots in reality: Geometric problems arise naturally in any computa- tional field that simulates or interacts with the physical world|computer graphics, robotics, geographic information systems, computer aided-design, and molecular modeling, to name a few|as well as in more abstract domains such as combinatorial geometry and algebraic topology. Aside from their obvious practical significance, geometric algorithms and data structures enjoy a rich and satisfying mathematical structure, and their development often requires tools from mathematical disciplines such as combinatorics, topology, and algebraic geometry, as well as traditional computational tools. The proposal outlines a challenging career development plan focusing on research in a broad cross-section of computational geometry, building on and significantly broadening the PI's successful work in the field over the last several years. Specific problem areas in which the PI plans to work include approximation algorithms, kinetic data structures, spatial and temporal databases, external memory computation, geometric optimization, and clustering. This classification is at best a rough guide, as many interesting geometric problems fall into more than one category. Furthermore, the PI plans to continue combining theory and empirical experimentation in his work, putting an emphasize on algorithms that perform well in practice.