Design, analysis and implementation of geometric and graph algorithms

点击翻译按钮获取中文摘要

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.