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

在现实世界中，寻找两个位置之间的最短路径是一个自然的问题。在当今信息时代，最短路径及相关问题在计算机和信息科学中得到了广泛的研究。然而，随着越来越多的应用需要在实践中出现，新的问题不断出现。其中，越来越多的问题存在于某些几何领域，这些问题源于机器人运动规划、交通运输、地理信息系统、物流、计算机图形学、计算机视觉、智能系统、设施选址、VLSI设计等应用。本项目旨在研究几何环境下的基本最短路径及相关问题。其目标是探索新的想法和见解，以开发有效的算法来解决这些问题。这个项目产生的研究成果将被整合到几门关于数据结构、算法和计算几何的课程中，这将使不同背景的研究生和本科生受益。该项目将培养研究生，并为本科生带来研究机会。更具体地说，该项目中的主题包括但不限于避开障碍物的最短路径及其许多变化、最小连接路径、测地线Voronoi图、几何设施选址等。其中一些问题已经有了现有的算法，该项目有望基于新的见解和技术开发更有效的解决方案。其他问题以前从未被研究过，这个项目有望为第一批已知的算法提供对这些问题的几何结构的深入理解。通过开发新的算法和技术，这项研究将在解决几何领域的最短路径和相关问题方面推进知识和取得进展。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.