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.