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

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

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.