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.

计算几何形状是理论计算机科学的分支，该分支致力于几何算法和数据结构的设计，分析和实施。 计算几何形状在现实中具有深厚的根源：几何问题自然出现在模拟或与物理世界互动的任何计算字段中 - - 计算机图形，机器人技术，地理信息系统，计算机辅助设计和分子建模，仅举几例 - 等于更多的抽象领域，例如结合层的微微分离和Algebraic topolaic和Algebraic topoloic topoloic topolaic topoloic topoloic topoloic。这项研究的重点是计算几何学的基本问题。这些问题包括设定，击球集，独立集和其他相关问题。 这些问题从无线网络到优化都有许多应用。这项研究的主要主题是结合``经典''计算几何技术（例如插条，epsilon-nets等）与操作研究中使用的技术（线性计划，圆形技术等）相结合的。这项研究旨在极大地改善我们对这些结构问题的理解。 这项研究可能会导致这些问题的近似算法改善。 从技术工作获得的算法和见解将使广泛使用几何算法的计算机科学和相关学科受益。 这项研究有可能通过将新技术引入该领域来扩大计算几何形状的范围。一本基于该奖项的研究的书将在不久的将来出版。这将使开发的技术可用于包括来自工程学，数学以及自然和社会科学的学生和研究人员组成的广泛受众。