Mathematical Sciences: Combinatorial Optimization and Graph Theory Problems in Geometry

最近爆发的计算几何和算法机器人领域已经证明了有效算法解决组合优化和图论问题的本质。很少有几何算法没有图论的成分，无论是在结构上还是在数据结构的使用上。本研究的主要目的是探索在机器人和计算机视觉应用中出现的几何问题，并利用图论的许多工具来解决这些问题。在某些情况下，需要制定和解决新的问题；在其他情况下，将调查当前使用的方法，看看是否有可能从图论概念和算法的应用中得到改进。基本目标是证明（最坏情况下）问题计算复杂性的界限，要么通过生成一个有效的算法（如果存在的话），要么通过证明“下界”（如np -硬度）。在np困难问题的情况下，目标是设计有效的启发式算法，如果可能的话，具有可证明的良好有效性。特别是，研究将包括机器人中最短路径和最短周期问题的重要变化，几何建模中的“美化”问题，图形和计算几何中出现的可见性问题，以及计算机视觉中出现的图像匹配问题。//

The recently erupting fields of computational geometry and algorithmic robotics have demonstrated the essential nature of efficient algorithms for problems in combinatorial optimization and graph theory. There are very few geometric algorithms that do not have some graph theoretic component, either in their very structure or in their use of data structures. The main thrust of this research is to explore geometric problems that arise in applications to robotics and computer vision, and bring to these problems the many tools of graph theory. In some cases, new problems need to be formulated and solved; in other cases, the methods currently being used will be investigated to see if there are possible improvements that may come from the application of graph theoretic concepts and algorithms. The basic goal is to prove (worse-case) bounds on the computational complexity of problems, either by producing an efficient algorithm if one exists, or by proving a "lower bound" such as NP-hardness. In cases of NP-hard problems, the goal is to devise efficient heuristic algorithms, if possible with provably good effectiveness. In particular, the investigation will include important variations on shortest path and shortest cycle problems in robotics, "beautification" problems in geometric modelling, visibility questions that arise in graphics and computational geometry, and image matching problems that arise in computer vision. //