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.

在过去的几十年中，在计算几何学领域取得了巨大进步。已经开发了有效的算法来解决几何问题。但是，计算几何形状中存在许多问题，这些问题尚未具有良好的算法，甚至没有任何算法解决方案。该项目的主要目的是开发用于解决这些几何问题的算法中的新基本技术。本项目旨在研究计算几何形状的一组特定问题：在飞机上多边形域（或多边形）中的问题。这些问题特别有趣且基本，因为它们对飞机中的许多几何问题进行了建模。具体问题包括通过欧几里得或其他指标测量的最短路径，最小链路路径，其他几何路径，地理伏罗尼亚图，可见性多边形，直径和中心，地球分解，多边形分解，设施，设施的位置以及几何数据结构以及靶向范围等方面的验证效果。这项研究将带来来自其他领域的多种方法，例如离散数学，图理论，操作研究，组合优化，计算复杂性，数据结构等。该项目有望大大提高我们对多边形领域中问题几何结构的理解，并生成解决这些问题的新算法工具。 这项研究将通过引入新技术来潜在地丰富计算几何形状领域。从项目获得的算法和观察结果还将受益于广泛使用几何算法的计算机科学和其他相关学科。该项目的另一个重要部分是培训研究生进行研究，尤其是在开发解决计算几何问题问题的算法时。