- Home
- Research Areas
- Biological Sciences (BIO)
- Computer and Information Science and Engineering (CISE)
- Education and Human Resources (EHR)
- Engineering (ENG)
- Environmental Research and Education (ERE)
- Geosciences (GEO)
- Integrative Activities (OIA)
- International Science and Engineering (OISE)
- Mathematical and Physical Sciences (MPS)
- Social, Behavioral and Economic Sciences (SBE)
- Funding
- About Funding
- Archived Funding Search
- Due Dates
- Find Funding
- Merit Review
- Policies and Procedures
- Preparing Proposals
- Recent Opportunities
- Transformative Research
- Related Links
- Proposal and Award Policies and Procedures Guide (PAPPG)
- Research.gov
- FastLane
- Funding Opportunities For
- Graduate Students
- K-12 Educators
- Postdoctoral Fellows
- Undergraduate Students
- Small Business
- Awards
- Document Library
- News
- About NSF
Award Abstract # 2005323
AF: Small: Algorithms for Geometric Shortest Paths and Related Problems
| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Awardee: |
|
| Initial Amendment Date: | July 24, 2020 |
| Latest Amendment Date: | July 24, 2020 |
| Award Number: | 2005323 |
| Award Instrument: | Standard Grant |
| Program Manager: |
A. Funda Ergun
fergun@nsf.gov (703)292-2216 CCF Division of Computing and Communication Foundations CSE Direct For Computer & Info Scie & Enginr |
| Start Date: | October 1, 2020 |
| End Date: | September 30, 2023 (Estimated) |
| Total Intended Award Amount: | $400,000.00 |
| Total Awarded Amount to Date: | $400,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Awardee Sponsored Research Office: |
1000 OLD MAIN HILL LOGAN UT US 84322-1000 (435)797-1226 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
4205 Old Main Hill Logan UT US 84322-4205 |
| Primary Place of Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
Wang, Haitao
"A new algorithm for Euclidean shortest paths in the plane"
Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
, 2021
https://doi.org/10.1145/3406325.3451037
Citation Details
Wang, Haitao
"An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons"
Proceedings of the 37th International Symposium on Computational Geometry (SoCG 2021)
, 2021
https://doi.org/10.4230/LIPIcs.SoCG.2021.59
Citation Details
Wang, Haitao and Zhao, Yiming
"Algorithms for Diameters of Unicycle Graphs and Diameter-Optimally Augmenting Trees"
Proceedings of the 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021)
, 2021
https://doi.org/10.1007/978-3-030-68211-8_3
Citation Details
Wang, Haitao
"Shortest Paths Among Obstacles in the Plane Revisited"
Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
, 2021
https://doi.org/10.1137/1.9781611976465.51
Citation Details
Please report errors in award information by writing to: awardsearch@nsf.gov.
