AF: Small: Computational Geometry from a Fine-Grained Perspective

AF：小：细粒度角度的计算几何

• 批准号: 2224271
• 负责人: Timothy Chan
• 金额: $ 60万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2224271&HistoricalAwards=false
• 关键词: AF; Small; Computational; Geometry; Fine

Many real-world problems require fast processing of large amounts of geometric data. Computational geometry is concerned with the design of efficient algorithms for solving such problems. Over the past four decades, a variety of algorithms have been developed for the most fundamental problems in the area, and in many cases, the amount of time used by these known algorithms are thought to be the best possible, or close to the best, in a fine-grained sense. Ideally, one would like to rigorously prove that no faster algorithm is possible, but unfortunately, such proofs are beyond reach under the current state of art. To circumvent this issue, researchers in theoretical computer science have recently turned to "conditional" proofs which assume certain unproved but believable hypotheses about the hardness of various "core" problems. The approach is to show that if a faster algorithm were to exist for the problem at hand, then we would get an unreasonably fast algorithm for one of the core problems, contradicting the hypotheses. In this project, the investigator will adopt this approach to better understand the fine-grained complexity of basic geometric problems. In addition, material from this project will be incorporated into courses on algorithms and computational geometry, and help in the training of several graduate students. The project will explore a variety of problems under this paradigm, about geometric optimization, geometric searching in low and moderate dimensions, static and dynamic geometric data structures, matching point clouds, etc. The main goal is to establish a web of new reductions between these geometric problems, as well as reductions from known core problems outside of geometry (such as 3SUM and shortest paths in graphs), in order to prove conditional lower bounds on the complexity of geometric problems. A parallel goal is to find better upper bounds, i.e., speed up existing algorithms, when possible. For example, one tool involves the use of algebraic decision trees. Conversely, geometric techniques might help researchers assess the believability of standard hypotheses, and new problems will be identified to enrich the interplay between computational geometry and other areas of algorithms.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.

许多现实世界的问题需要快速处理大量的几何数据。计算几何关注的是解决此类问题的有效算法的设计。在过去的四十年中，针对该领域最基本的问题开发了多种算法，并且在许多情况下，这些已知算法所使用的时间量被认为是可能的最佳或接近最佳，从细粒度的意义上来说。理想情况下，人们希望严格证明没有更快的算法是可能的，但不幸的是，在当前的技术水平下，这样的证明是无法实现的。为了规避这个问题，理论计算机科学的研究人员最近转向“条件”证明，这些证明对各种“核心”问题的难度提出了某些未经证实但可信的假设。该方法是为了表明，如果针对当前的问题存在更快的算法，那么我们将针对其中一个核心问题得到一种不合理的快速算法，这与假设相矛盾。在这个项目中，研究者将采用这种方法来更好地理解基本几何问题的细粒度复杂性。此外，该项目的材料将被纳入算法和计算几何课程中，并帮助培训几名研究生。 该项目将探索该范式下的各种问题，包括几何优化、低维和中等维度的几何搜索、静态和动态几何数据结构、匹配点云等。主要目标是在这些之间建立一个新的简化网络几何问题，以及几何之外已知核心问题的简化（例如 3SUM 和图中的最短路径），以证明几何问题复杂性的条件下界。一个并行的目标是找到更好的上限，即在可能的情况下加快现有算法的速度。例如，一种工具涉及代数决策树的使用。相反，几何技术可能有助于研究人员评估标准假设的可信度，并且将发现新的问题，以丰富计算几何与算法其他领域之间的相互作用。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准。

项目成果

Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

Fredman 的技巧与主导产品的结合：未加权 APSP、3SUM 计数等的细粒度复杂性

• DOI: 10.1145/3564246.3585237
• 发表时间: 2023-06
• 期刊: Proc. 55th ACM Sympos. Theory of Computing (STOC
• 作者: Chan, Timothy M.;Vassilevska Williams, Virginia;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan

Simpler reductions from Exact Triangle.

精确三角形的简化更简单。

• 发表时间: 2024-01
• 期刊: Proc. 7th SIAM Sympos. Simplicity of Algorithms (SOSA
• 作者: Chan, Timothy M.;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan

An optimal algorithm for higher-order Voronoi diagrams in the plane: The usefulness of nondeterminism

平面中高阶 Voronoi 图的优化算法：非确定性的有用性

• 发表时间: 2024-01
• 期刊: Proc. 35th ACM-SIAM Sympos. Discrete Algorithms (SODA
• 作者: Chan, Timothy M.;Cheng, Pingan;Zheng, Da Wei
• 通讯作者: Zheng, Da Wei

Minimum L_∞ Hausdorff distance of point sets under translation: Generalizing Klee's measure problem

平移点集的最小 L_Hausdorff 距离：推广克利测度问题

• DOI: 10.4230/lipics.socg.2023.24
• 发表时间: 2023-06
• 期刊: Proc. 39th Sympos. Computational Geometry (SoCG
• 作者: Chan; Timothy M.
• 通讯作者: Timothy M.

Finding triangles and other small subgraphs in geometric intersection graphs.

在几何相交图中查找三角形和其他小子图。

• 发表时间: 2023-01
• 期刊: Proc. 34th ACM-SIAM Sympos. Discrete Algorithms (SODA
• 作者: Chan; Timothy M.
• 通讯作者: Timothy M.