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.