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的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

Simpler Reductions from Exact Triangle

精确三角形的更简单简化

• 发表时间: 2023
• 期刊: SIAM Symposium on Simplicity in Algorithms
• 作者: Timothy M. Chan;Yinzhan Xu
• 通讯作者: Yinzhan Xu

Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs

• DOI: 10.48550/arxiv.2211.05345
• 发表时间: 2022-11
• 作者: Timothy M. Chan

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

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

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

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

• DOI: 10.48550/arxiv.2310.15363
• 发表时间: 2023-10
• 期刊: ArXiv
• 作者: Timothy M. Chan;Pingan Cheng;Da Wei Zheng

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
• 期刊: Proc. 55th ACM Sympos. Theory of Computing (STOC
• 作者: Chan, Timothy M.;Vassilevska Williams, Virginia;Xu, Yinzhan
• 通讯作者: Xu, Yinzhan