CAREER: Approximation Algorithms for Geometric Computing

职业：几何计算的近似算法

• 批准号: 0132901
• 负责人: Sariel Har-Peled
• 金额: $ 32.5万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-05-01 至 2008-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0132901&HistoricalAwards=false
• 关键词: CAREER; Approximation; Algorithms; 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.

0132901Har-Peled, Sariel伊利诺伊大学厄巴纳-香槟分校计算几何是理论计算机科学的一个分支，致力于几何算法和数据结构的设计、分析和实现。计算几何在现实中有很深的根源：几何问题自然出现在任何模拟物理世界或与物理世界交互的计算领域|计算机图形学、机器人技术、地理信息系统、计算机辅助设计和分子建模等等|以及例如组合几何和代数拓扑学等更抽象的领域。除了明显的实际意义外，几何算法和数据结构还拥有丰富且令人满意的数学结构，其发展往往需要组合数学、拓扑学、代数几何等数学学科的工具以及传统的计算工具。该提案概述了具有挑战性的职业发展该计划重点关注国外计算几何领域的研究，以 PI 过去几年在该领域的成功工作为基础并显着扩展。 PI 计划工作的具体问题领域包括近似算法、动力学数据结构、空间和时间数据库、外部存储器计算、几何优化和聚类。这种分类充其量只是一个粗略的指导，因为许多有趣的几何问题属于多个类别。此外，PI 计划在他的工作中继续将理论和实证实验结合起来，重点关注在实践中表现良好的算法。