CAREER: Algorithmic issues in geometric network optimization, binary space partitions, and metamorphic systems

人们正在研究已知问题的新变体(如旅行商、用于空间细分的二进制空间划分和几何膨胀)，以产生新的技术并解决算法设计和逼近中的关键问题。除此之外，它们还可能产生其他影响。例如，几何膨胀的研究可能会为设计交通网络提供更好的方法，并为升级现有的交通网络提供有效的方法。变质系统的理论研究对于理解它们的能力和开发控制它们的算法是必要的。这项研究的一个重要方面是促进不同领域的技术的整合-离散和组合几何、几何图论、图论、拓扑学、线性规划-在几何算法的设计中。这项研究涉及计算几何和机器人领域的算法问题，分为三个方向。第一类问题是几何网络优化领域，重点是过去十年出现的经典旅行商问题的新变种，如有邻域的问题和角度限制的旅行问题。这些努力的目的是了解不同类别区域之间的差异，这使得某些情况比其他情况更难接近。第二个研究方向涉及应用于两个重要问题的切割技术：二进制空间划分和库存切割算法。第三类包括变形机器人系统的研究和分析产生的基本问题，这是机器人学中一个相对较新的研究方向。研究了变质系统的两种基本能力：重构和运动。由于它们的通用性和高度的容错性，这类系统的开发被认为是非常有前途的。这项研究的一个重要方面是促进不同领域的技术的整合-离散和组合几何、几何图论、图论、拓扑学、线性规划-在几何算法的设计中。

The new variants of known problems (like traveling salesman, binary space partitions for space subdivisions, and geometric dilation) are being studied in order to produce new techniques and address key issues in algorithm design and approximation. Besides that, they are likely to have other implications. For example, the study of geometric dilation may provide better ways of designing transportation networks, and efficient ways for upgrading existing ones. The theoretical study of metamorphic systems is necessary for understanding their capabilities and for developing algorithms that control them. An important aspect of this research is advancing the integration of techniques from different areas --- discrete and combinatorial geometry, geometric graph theory, graph theory, topology, linear programming --- in the design of geometric algorithms. This research deals with algorithmic questions from the areas of computational geometry and robotics, grouped in three directions. The problems in the first category are in the area of geometric network optimization where the focus will be new variants of the classic traveling salesman problem that have emerged in the last decade, such as those with neighborhoods and the angle restricted tour problem. These efforts are aimed at understanding the differences between various classes of regions, which make some instances harder to approximate than others. A second research direction deals with cutting techniques applied to two important problems: binary space partitions and stock cutting algorithms. A third category includes fundamental questions generated by the study and analysis of metamorphic robotic systems, a relatively new research direction in robotics. Two basic capabilities of metamorphic systems are researched: reconfiguration and locomotion. Development of such systems is regarded as very promising, due to their versatility and high degree of fault tolerance. An important aspect of this research is advancing the integration of techniques from different areas --- discrete and combinatorial geometry, geometric graph theory, graph theory, topology, linear programming --- in the design of geometric algorithms.