AF: Small: Towards Sturdier Geometric Algorithms

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.