Mathematical Sciences: Combinatorial Optimization and Graph Theory Problems in Geometry

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

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