AF: Small: Algorithms for Geometric Shortest Paths and Related Problems

Finding a shortest path between two locations is a natural problem in the real world. In today's information age, shortest path and related problems have been extensively studied in computer and information science. Yet new problems keep emerging as more and more applications are desired in practice. Among them, a growing number of problems lie in certain geometric domains, which originate from applications such as robot motion planning, transportation, geographic information systems, logistics, computer graphics, computer vision, intelligent systems, facility locations, VLSI design, etc. This project aims to study fundamental shortest path and related problems in geometric settings. The goal is to explore novel ideas and insights to develop efficient algorithms to solve these problems. Research results produced from this project will be integrated into several courses on data structures, algorithms, and computational geometry, which will benefit both graduate and undergraduate students with diverse backgrounds. This project will train graduate students as well as bring research opportunities to undergraduate students. More specifically, the topics in the project include, but are not limited to, shortest paths avoiding obstacles and many of variations thereof, minimum-link paths, geodesic Voronoi diagrams, geometric facility locations, etc. Some of these problems already have existing algorithms, and this project is expected to develop more efficient solutions based on new insights and techniques. Others have never been studied before, and this project is expected to provide first-known algorithms with an in-depth understanding of the geometric structures of these problems. By developing new algorithms and techniques, this research will advance knowledge and make progress on solving shortest path and related problems in geometric domains. 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.