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

AF：小：几何最短路径算法及相关问题

• 批准号: 2300356
• 负责人: Haitao Wang
• 金额: $ 40万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2300356&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Geometric; Shortest

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.

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

项目成果

A New Algorithm for Euclidean Shortest Paths in the Plane

平面上欧几里得最短路径的新算法

• DOI: 10.1145/3580475
• 发表时间: 2023-04
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Wang; Haitao
• 通讯作者: Haitao

Geometric Hitting Set for Line-Constrained Disks

用于线约束盘的几何击球组

• 发表时间: 2023-08
• 期刊: Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023
• 作者: Liu, Gang;Wang, Haitao
• 通讯作者: Wang, Haitao

Reverse shortest path problem for unit-disk graphs

单位圆盘图的逆向最短路径问题

• 发表时间: 2023-04
• 期刊: Journal of computational geometry
• 作者: Wang, Haitao;Zhao, Yiming
• 通讯作者: Zhao, Yiming

Improved Algorithms for Distance Selection and Related Problems

距离选择及相关问题的改进算法

• 发表时间: 2023-08
• 期刊: Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023
• 作者: Wang, Haitao;Zhao, Yiming
• 通讯作者: Zhao, Yiming

Dynamic Convex Hulls Under Window-Sliding Updates

窗口滑动更新下的动态凸包

• 发表时间: 2023-08
• 期刊: Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023
• 作者: Wang; Haitao
• 通讯作者: Haitao