AF: Small: Splines on Optimal Crystallographic Lattices

晶格是自然界将空间划分为具有高度对称性的均匀晶胞的方式。平面的等边三角剖分，三维的面心和体心立方网格，四维的基于24单元的网格，所有的划分空间都比常用的笛卡尔网格更加各向同性。更高的各向同性意味着更高的效率，因为更稀疏的数据允许在笛卡尔网格上复制与数据相同的功能。为了利用这种提高的效率，对于材料、医学、生物甚至代数计算，我们需要探索和制作可实际使用的、尊重晶体晶格结构的多变量“晶体”样条线。这项研究的重点是从3维到8维，其中样条系数的数量仍然是可管理的，本研究试图推导出计算工具、数据结构和算法的有效模拟，这些计算工具、数据结构和算法目前仅适用于笛卡尔网格上的张量积样条。这包括支持重建的准内插、泛函求值、精化和自适应细分、奇点存在时的多分辨率、转换为局部多项式形式以及结构奇点的处理的算法和数据结构。作为概念的证明和本身的扩展，这些工具将在多变量代数实根求法、水平集的误差界近似、广义细分和偏微分方程组的计算公式上进行测试。基本理论、算法和编码实例的分离将降低使用晶体样条法的障碍，从而使模拟和建模的计算更有效。实根求法的进展将有利于从几何约束求解到绘制分子构象空间的应用。在求解晶格上的微分方程组时，基于晶体样条线的有限元将尊重边界数据。令人印象深刻的晶格结构将吸引本科生和研究生参加数字艺术和计算机图形学课程；更高维度的体积飞行和投影的视频将使更广泛的公众能够接触到这项研究。

Crystallographic lattices are nature's way to partition space into uniform cells with high symmetry. The equilateral triangulation of the plane, the face-centered and the body-centered cubic lattice in 3D and the lattice based on the 24-cell in 4D, all partition space more isotropically than the commonly-used Cartesian grid. Higher isotropy means higher efficiency, in that sparser data allows reproducing the same functions as data on the Cartesian grid. To take advantage of this increased efficiency, for material, medical, biological and even algebraic computations, we need to explore and make practically accessible multi-variate `crystallographic' splines that honor the structure of the crystallographic lattices. With emphasis on dimensions 3 through 8, where the number of spline coefficients is still manageable, this research seeks to derive efficient analogues of the computational tools, data structures and algorithms that are currently available only for tensor-product splines on Cartesian grids. This includes algorithms and data structures to support quasi-interpolation for reconstruction, evaluation of functionals, refinement and adaptive subdivision, multi-resolution in the presence of singularities, conversion to localized polynomial form, and treatment of structural singularities. As proof of concept and extensions in their own right, these tools will be tested on multi-variate algebraic real-root finding, error-bounded approximation of level-sets, generalized subdivision and the computational formulation of partial differential equations.Dissemination of the underlying theory, algorithms and coded examples will lower the barrier for the use of crystallographic splines and thereby enable more efficient computing for simulation and modeling. Progress in real root finding will benefit applications from geometric constraint solving to charting molecular conformation spaces. Finite elements based on crystallographic splines will honor boundary data when solving differential equations on crystallographic lattices. The impressive structure of crystallographic lattices will engage undergraduate and graduate students in digital arts and computer graphics classes; and videos of volumetric fly-throughs and projections from higher dimensions will make this research accessible to the wider public.