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.

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