Mathematical Sciences: Combinatorial Optimization and Graph Theory Problems in Geometry

数学科学：几何中的组合优化和图论问题

• 批准号: 8903304
• 负责人: Esther Arkin
• 金额: $ 4.9万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-15 至 1991-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8903304&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Combinatorial; Optimization; Graph

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

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