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

AF:Medium:RUI:运动距离几何中的算法问题

• 批准号: 2212309
• 负责人: Ileana Streinu
• 金额: $ 60万
• 依托单位: Smith College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212309&HistoricalAwards=false
• 关键词: AF; Medium; RUI; Algorithmic; Problems

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.

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

项目成果

Computing Circuit Polynomials in the Algebraic Rigidity Matroid

代数刚性拟阵中计算电路多项式

• DOI: 10.1137/21m1437986
• 发表时间: 2023-06
• 期刊: SIAM Journal on Applied Algebra and Geometry
• 影响因子: 1.2
• 作者: Malić, Goran;Streinu, Ileana
• 通讯作者: Streinu, Ileana

Saturation and periodic self-stress in geometric auxetics

几何拉胀中的饱和度和周期性自应力

• DOI: 10.1098/rsos.220765
• 发表时间: 2022-08
• 期刊: Royal Society Open Science
• 影响因子: 3.5
• 作者: Borcea, Ciprian S.;Streinu, Ileana
• 通讯作者: Streinu, Ileana