AF: Small: Towards Sturdier Geometric Algorithms

计算几何是理论计算机科学的分支，致力于设计、分析和实现几何算法和数据结构。 几何无处不在：几何问题在任何模拟物理世界或与物理世界交互的计算领域中自然出现。 计划中的研究重点是设计算法的基本问题，这些算法是鲁棒的，可以承受（潜在的灾难性）故障。故障可能包括网络故障、数据损坏或数据噪声。从技术工作中获得的算法和见解将使计算机科学和广泛使用几何算法的相关学科受益。 该项目将支持和培训至少两个新的博士生在计算几何在UIUC。此外，该项目还将培训代表性不足的本科生。 本项目拟研究的问题包括：（i）可靠的空间，即使在节点的灾难性故障之后也保持良好的空间，（ii）计算点的良好排序，使得可以直接在这些排序上解决各种问题，（iii）对凸范围进行采样，（iv）几何优化，其中隐式地提供输入，（v）通过Ham-Sandwich切割的几何分割，该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Computational geometry is the branch of theoretical computer science devoted to the design, analysis, and implementation of geometric algorithms and data structures. Geometry is everywhere: geometric problems arise naturally in any computational field that simulates or interacts with the physical world. The planned research focuses on the fundamental problem of designing algorithms that are robust and can withstand (potentially catastrophic) failure. Failure might range from network failure, corruption of data, or data being noisy. The algorithms and insights obtained from the technical work will benefit computer science and related disciplines where geometric algorithms are widely used. The project will support and train at least two new PhD students in Computational Geometry at UIUC. In addition, the project would train underrepresented undergraduate students. The problems to be studied in this project include: (i) reliable spanners, which remain good spanners even after a catastrophic failure of nodes, (ii) computing good orderings of points, such that various problems can be solved directly on these orders, (iii) sampling for convex ranges, (iv) geometric optimization where the input is provided implicitly, (v) geometric partitioning via Ham-Sandwich cuts, and efficient geometric algorithms for such problems, and (vi) handling outliers for various geometric optimization problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.