AF: Small: Collaborative Research: Reconfiguration Algorithms

计算几何使用图形、多边形和排列来模拟物理对象和现象。有些物体本身是灵活的(例如蛋白质和机械臂)，另一些物体是静止的，但需要定期调整(例如通信和运输网络)。这个项目的重点是重新配置。目标是描述、理解和控制几何构型中的组合、几何和拓扑变化。本研究项目将在三个方面开发修改几何构形的新算法和数据结构：(1)几何对象构形空间中的优化问题，包括图形增强、经典TSP巡回问题的变体和多准则网络设计。(2)离散移动重构，当前的挑战包括设计高效的数据结构来支持配置空间中的最短路径计算，近似配置空间的直径和半径，以及确定是否可以重构。(3)连续运动建模，包括杆关节框架、铰链多边形和圆盘排列的运动规划算法和相应的动态数据结构，受蛋白质折叠应用的启发。离散和连续重构问题的统一方法允许将复杂系统分解为基本操作，这反过来又导致更高效的计算工具。来自两所大学的教职员工和学生之间的合作确保了高质量的培训，并为所有参与的学生打开了新的机会。

Computational geometry uses graphs, polygons, and arrangements to model physical objects and phenomena. Some of the objects are inherently flexible (e.g., proteins and robotic arms), others are stationary but require adjustments on a regular basis (e.g., communication and transportation networks). The focus of this project is on reconfigurations. The goal is to describe, understand, and control the combinatorial, geometric and topological changes in geometric configurations. This research project will develop new algorithms and data structures for modifying geometric configurations in three areas: (1) Optimization problems for in the configuration space of geometric objects, including graph augmentation, variations of the classical TSP tour problem, and network design for multiple criteria. (2) Reconfiguration through discrete moves, where current challenges include designing efficient data structures to support shortest path computation in the configuration space, approximating the diameter and radius of configuration spaces, and deciding whether reconfiguration is possible. (3) Modeling continuous motion, which includes motion planning algorithms and corresponding dynamic data structures for bar-and-joint frameworks, hinged polygons, and disk arrangements, motivated by applications in protein folding. A unified approach to discrete and continuous reconfiguration problems allows breaking down complex systems into elementary operations, which in turn leads to more efficient computational tools. The collaboration between faculty members and students from two universities ensures a high quality of training and opens new opportunities for all participating students.