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

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

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.