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

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

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.