AF: Small: Collaborative Research: Reconfiguration Algorithms

点击翻译按钮获取中文摘要

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.