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.