CAREER: Approximation Algorithms for Geometric Computing

点击翻译按钮获取中文摘要

0132901Har-Peled, SarielU of Ill, Urbana-ChampaignComputational geometry is the branch of theoretical computer science devoted to the design,analysis, and implementation of geometric algorithms and data structures. Computationalgeometry 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 namea few|as well as in more abstract domains such as combinatorial geometry and algebraictopology. Aside from their obvious practical significance, geometric algorithms and datastructures enjoy a rich and satisfying mathematical structure, and their development oftenrequires tools from mathematical disciplines such as combinatorics, topology, and algebraicgeometry, as well as traditional computational tools.The proposal outlines a challenging career development plan focusing on research in abroad cross-section of computational geometry, building on and significantly broadening thePI's successful work in the field over the last several years. Specific problem areas in whichthe PI plans to work include approximation algorithms, kinetic data structures, spatial andtemporal databases, external memory computation, geometric optimization, and clustering.This classification is at best a rough guide, as many interesting geometric problems fallinto more than one category. Furthermore, the PI plans to continue combining theory andempirical experimentation in his work, putting an emphasize on algorithms that performwell in practice.