Design, analysis and implementation of geometric and graph algorithms

我们将设计、分析和实现计算几何和图形算法中出现的问题的算法。只要有可能，我们将根据所使用的计算资源（时间、空间、处理器、I/ o）显示上限和下限，提供正确性的证明，并显示最优性或近似界限。我们将要学习的问题很可能是对实践中出现的问题的抽象、简化或概括。在计算几何中，我们将主要关注最短路径问题、扳手、约束几何查询和数据结构。在图算法中，重点将放在平面分隔符、几何与图论交界的问题、理解几何扳手的图论性质、设计基于几何图的问题的算法，特别是研究底层问题域为几何的图问题。在接下来的五年里，我们希望通过设计三维加权最短路径问题的算法，将权重要求从固定推广到连续，找到一个合适的三角剖分来导致给定的最短路径距离，并找到实际相关的算法，来扩展我们在多面体域上的几何最短路径问题的现有工作。我们将通过设计满足有用的图论性质的约束域的扳手来扩展我们对几何扳手的研究工作，这可能会导致更快的算法。我们将进一步扩展我们在“局部几何查询”方面的工作（例如，找到包含查询点的最大空圆）。基于Frechet距离（这是两条曲线之间非常常用的相似性度量）的问题及其变体的速度约束版本将进一步探索。我们的一些算法和技术可以应用于设计经济高效的网络，在地理域中寻找短的、时间最优的路径，以及简洁地表示几何数据以有效地回答查询的方法。

We will design, analyze and implement algorithms for problems arising in computational geometry and graph algorithms. Wherever possible, we will show upper and lower bounds in terms of computing resources used (time, space, processors, I/Os), provide the proof of correctness, and show the optimality or approximation bounds. The problems that we will study will likely be an abstraction, or a simplification or a generalization of problems that occur in practice. In computational geometry, we will primarily focus on shortest path problems, spanners, constrained geometrical queries and data structures. In graph algorithms, the focus will be on planar separators, problems that are at the interface of geometry and graph theory, understanding graph theoretic properties of geometric spanners, designing algorithms for problems based on geometric graphs, and especially studying graph problems where the underlying problem domain is geometric. Over the next five years, we want to expand our existing work on geometric shortest path problems on polyhedral domains by designing algorithms for three-dimensional weighted shortest path problems, generalizing the weight requirements from fixed to continuous, finding a suitable triangulation which leads to the given shortest path distances, and finding practically-relevant algorithms. We will expand our research work on geometric spanners by designing spanners for constrained domains that satisfy useful graph-theoretic properties that will likely lead to faster algorithms. We will further expand our work on `localized geometric queries' (e.g., find the largest empty circle containing a query point). The speed-constrained versions of the Frechet distance (which is a very commonly used similarity measure between two curves) based problems and their variants will be further explored. Some of our algorithms and techniques may find applications in designing economical and efficient networks, finding short, time-optimum, paths in geographical domains, and ways to represent geometric data succinctly to answer queries efficiently.