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

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

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.