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

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

• 批准号: 2005323
• 负责人: Haitao Wang
• 金额: $ 40万
• 依托单位: Utah State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2005323&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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Unit-Disk Range Searching and Applications

单位圆盘范围搜索及应用

• DOI: 10.4230/lipics.swat.2022.32
• 发表时间: 2022
• 期刊: Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022
• 作者: Wang, Haitao

Reverse Shortest Path Problem for Unit-Disk Graphs

• DOI: 10.1007/978-3-030-83508-8_47
• 发表时间: 2021-04
• 作者: Haitao Wang;Yiming Zhao

Algorithms for the line-constrained disk coverage and related problems

线路约束磁盘覆盖算法及相关问题

• DOI: 10.1016/j.comgeo.2022.101883
• 发表时间: 2022
• 期刊: Computational Geometry
• 作者: Pedersen, Logan;Wang, Haitao
• 通讯作者: Wang, Haitao

A new algorithm for Euclidean shortest paths in the plane

平面内欧氏最短路径的新算法

• DOI: 10.1145/3406325.3451037
• 发表时间: 2021
• 期刊: Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021
• 作者: Wang, Haitao

An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons

简单多边形测地最远点Voronoi图的最优确定性算法

• DOI: 10.1007/s00454-022-00424-6
• 发表时间: 2023
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Wang, Haitao