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

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.