Mathematical Sciences: Combinatorial Optimization and Graph Theory Problems in Geometry

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

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. //