CAREER: Approximation Algorithms for Geometric Computing

计算几何是理论计算机科学的一个分支，致力于几何算法和数据结构的设计、分析和实现。计算几何在现实中有着深厚的根基：几何问题自然地出现在任何模拟或与物理世界交互的计算领域中：计算机图形学、机器人学、地理信息系统、计算机辅助设计和分子建模等等，以及更抽象的领域，如组合几何和代数拓扑学。除了它们明显的实际意义外，几何算法和数据结构享有丰富和令人满意的数学结构，它们的发展往往需要组合数学、拓扑学和代数几何等数学学科的工具，以及传统的计算工具。该提案概述了一个具有挑战性的职业发展计划，专注于计算几何在国外的横截面研究，建立在过去几年PI在该领域的成功工作的基础上，并显著拓宽了该领域的工作范围。PI计划解决的具体问题领域包括近似算法、动力学数据结构、空间和时间数据库、外部存储器计算、几何优化和集群。这种分类充其量只是一个粗略的指导，因为许多有趣的几何问题属于不止一个类别。此外，PI计划在他的工作中继续将理论和实证实验结合起来，重点放在在实践中表现良好的算法上。

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.