AF:Medium:RUI:Algorithmic Problems in Kinematic Distance Geometry

这个项目所解决的问题是由具体的计算问题所引起的，其中包括晶体学和材料科学。研究对象是运动受距离约束的动态点集。它们出现在科学和工程的多个领域，包括计算机辅助设计（CAD），机器人技术，传感器网络，结构分子生物学和材料科学。该项目中的问题有可能有助于阐明物质的基本性质，例如晶体中的相变，并可能导致发现或设计新的拉胀超材料（具有不寻常的变形特性的材料，在自然界中很少发现）。第一个方向是晶体学中出现的问题，包括刚性或柔性晶体的比较，周期性框架的超刚性，由有限到周期性方法产生的拉胀材料设计，最小刚性图的嵌入和更有效的算法用于计算周期性框架的刚性和柔性参数。第二个方向是开发有效的运动学设计的算法，其中的运动的几何对象的距离约束（框架）被分解成一个有限的集合的轨迹所产生的相关的一个自由度的框架，每个部署一个特定的，有限的时间间隔。该运动是由新的组合数学基础的代数约束，并导致有效和高效的算法设计的几何结构和运动学行为（运动）。这里开发的算法可以转化为满足这些需求的软件工具。该项目建立在研究人员，学生和合作者获得或开发的数学结果，算法和软件的基础上。它依赖于并结合了几个领域的想法：组合刚性，距离几何和计算代数几何。在数学上，研究人员最近成功地克服了Groebner基方法所带来的巨大挑战，并在2D Cayley-Menger理想中进行了以前无法实现的计算。这些最近的结果打开了新的计算机实验的可能性，预计将导致以前未观察到的数学特性，将被用于解决选定的距离几何学和运动学的开放问题。不同的学生群体已经并将继续参与这项研究，部分研究是在一所在STEM教育方面享有持久声誉的女子学院进行的。研究者还将继续让她的学生参与新教材的开发，使非专业人员能够获得研究结果，并将通过出版物、教程和讲座在多个科学领域和不同的受众中积极传播这些结果。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

The problems addressed by this project are motivated by concrete computational questions arising, among others, in crystallography and materials science. The objects of study are dynamic point sets whose motion is subject to distance constraints. They arise in multiple areas of science and engineering, including computer-aided design (CAD), robotics, sensor networks, structural molecular biology and materials science. The problems in this project have the potential to help elucidate fundamental properties of matter, such as phase transitions in crystals, and could lead to the discovery or to the design of new auxetic metamaterials (which are materials with unusual deformation properties, rarely found in nature). A first direction is on problems arising in Crystallography, including comparison of rigid or flexible crystals, ultra-rigidity of periodic frameworks, auxetic-material designs produced by finite-to-periodic methods, embeddings of minimal rigid graphs and more efficient algorithms for computing rigidity and flexibility parameters of periodic frameworks. A second direction is to develop efficient algorithms for kinematic design, where the motion of a geometric object subject to distance constraints (framework) is decomposed into a finite collection of trajectories arising from related one-degree-of-freedom frameworks, each deployed for a specific, finite interval of time. The motion is guided by novel combinatorics underlying the algebraic constraints and leads to effective and efficient algorithms for designing both the geometric structure and its kinematic behavior (motions). The algorithms developed here are amenable to be turned into software tools for these needs. The project builds upon mathematical results, algorithms and software obtained or developed by the investigator, students and collaborators. It relies on and combines ideas from several areas: combinatorial rigidity, distance geometry and computational algebraic geometry. Algorithmically, the investigator has recently succeeded in overcoming enormous challenges posed by Groebner-basis methods and carried out previously unattainable calculations in the 2D Cayley-Menger ideal. These very recent results open the possibility for novel computer experiments, anticipated to lead to previously unobserved mathematical properties that will be put to use in addressing the selected open questions in distance geometry and kinematics. A diverse population of students have been and will continue to be engaged in this research, conducted in part at an all-women college with a sustained reputation in STEM education. The investigator will also continue engaging her students in the development of new educational materials that will make the results accessible to non-specialists, and will actively disseminate them via publications, tutorials and talks in several scientific fields and to diverse audiences.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.