AF: Small: Algorithms for Computational Geometry Problems in Polygonal Domains

AF：小：多边形域中计算几何问题的算法

• 批准号: 1317143
• 负责人: Haitao Wang
• 金额: $ 33.8万
• 依托单位: Utah State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1317143&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Computational; Geometry

Tremendous progress has been made in the field of computational geometry in the last few decades. Efficient algorithms have been developed to solve geometric problems. However, there are many problems in computational geometry that do not yet have good algorithms or even do not have any algorithmic solutions. The main goal of this project is the development of new fundamental techniques in algorithms for solving those geometric problems.This project aims to investigate a particular group of problems in computational geometry: problems in polygonal domains (or polygons with holes) in the plane. These problems are particularly interesting and fundamental because they model many geometric problems in the plane. The specific problems include computing shortest paths measured by Euclidean or other metrics, minimum link paths, other geometric paths, geodesic Voronoi diagrams, visibility polygons, geodesic diameter and center, polygon decomposition, facility locations, and geometric data structures, etc. The goal is to develop new algorithmic techniques for solving these problems efficiently. This research will bring diverse methodologies from other areas such as discrete mathematics, graph theory, operations research, combinatorial optimization, computational complexity, data structures, etc. The project is expected to greatly improve our understanding of the geometric structures of the problems in polygonal domains and to produce new algorithmic tools for solving these problems. This research will potentially enrich the area of computational geometry by introducing new techniques. The algorithms and observations obtained from the project will also benefit computer science and other related disciplines where geometric algorithms are widely used. Another important part of this project is to train graduate students to practice in doing research, especially in developing algorithms for solving problems in computational geometry.

过去几十年来，计算几何领域取得了巨大进展。已经开发出有效的算法来解决几何问题。然而，计算几何中有很多问题还没有好的算法，甚至没有任何算法解决方案。该项目的主要目标是开发解决这些几何问题的算法中的新基础技术。该项目旨在研究计算几何中的一组特定问题：平面中的多边形域（或带孔的多边形）中的问题。这些问题特别有趣且基础，因为它们模拟了平面上的许多几何问题。具体问题包括计算欧几里德或其他度量测量的最短路径、最小链路路径、其他几何路径、测地线Voronoi图、可见性多边形、测地线直径和中心、多边形分解、设施位置和几何数据结构等。目标是开发新的算法技术来有效地解决这些问题。这项研究将带来离散数学、图论、运筹学、组合优化、计算复杂性、数据结构等其他领域的多种方法论。该项目有望极大地提高我们对多边形域问题的几何结构的理解并产生新的算法工具来解决这些问题。 这项研究将通过引入新技术潜在地丰富计算几何领域。从该项目中获得的算法和观察结果也将有益于计算机科学和其他广泛使用几何算法的相关学科。该项目的另一个重要部分是培训研究生进行研究实践，特别是开发解决计算几何问题的算法。