AF: Small: Approximation, Covering and Clustering in Computational Geometry

AF：小：计算几何中的近似、覆盖和聚类

• 批准号: 0915984
• 负责人: Sariel Har-Peled
• 金额: $ 41万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915984&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Covering; Clustering

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 computational 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. This research focuses on fundamental problems in computational geometry. These problems include set-cover, hitting set, independent set, and other related problems. These problems have numerous applications from wireless networking to optimization.The main theme of this research is to combine ``classical'' Computational Geometry techniques (like cuttings, epsilon-nets, etc) together with techniques used in Operation Research (Linear Programming, rounding techniques, etc).This research aims to greatly improve our understanding of the structure of these fundamental problems. The research may lead to improved approximation algorithms for these problems. The algorithms and insights obtained from the technical work will benefit computer science and related disciplines where geometric algorithms are widely used. This research has potential to broaden the scope of Computational Geometry by introducing new techniques into the field. A book partially based on the research in this award will be published in the near future. This will make the developed techniques available to wide audience consisting of students and researchers from several disciplines include engineering, mathematics, and the natural and social sciences.

计算几何是理论计算机科学的一个分支，致力于几何算法和数据结构的设计、分析和实现。 计算几何在现实中有很深的根源：几何问题自然出现在任何模拟物理世界或与物理世界交互的计算领域中——计算机图形学、机器人技术、地理信息系统、计算机辅助设计和分子建模等等—— ——以及更抽象的领域，例如组合几何和代数拓扑。本研究重点关注计算几何中的基本问题。这些问题包括设置覆盖、击球设置、独立设置以及其他相关问题。 这些问题有从无线网络到优化的众多应用。这项研究的主题是将“经典”计算几何技术（如切割、epsilon 网等）与运筹学中使用的技术（线性规划、舍入）相结合这项研究旨在大大提高我们对这些基本问题结构的理解。 该研究可能会改进这些问题的近似算法。 从技术工作中获得的算法和见解将有益于计算机科学和广泛使用几何算法的相关学科。 这项研究有可能通过将新技术引入该领域来扩大计算几何的范围。部分基于该奖项研究的书将于不久的将来出版。这将使开发的技术可供包括工程、数学、自然科学和社会科学等多个学科的学生和研究人员在内的广大受众使用。