Surface modeling, approximation theory, and coding theory

这项建议的重点是在应用数学的问题，可能会受到攻击，使用代数方法。有三个主题：（1）信息传递与编码理论;（2）有理曲面造型与隐式化;（3）逼近理论与多维样条。 该项目的主要目标是将抽象机器的全部力量用于这些主题;解决应用问题的关键往往是从不同的角度看待它。 例如，在过去的工作中，PI使用谱序列和局部上同调来研究样条;在编码理论中，PI使用复曲面几何和Cayley-Bacharach理论来获得从代数几何获得的某些代码的良好界限。该项目的编码理论部分将侧重于从三维或三维以上的复曲面中找到最佳编码;在样条方面，PI将研究多面体复合体上的样条，以及Groebner基算法作为样条计算的符号代数前端的功效。最后，计算机科学（特别是计算机视觉和动画）和代数之间令人兴奋的新交互涉及有理曲面建模：如果一个地图由三个有理函数从平面到三维空间定义，那么在图像上消失的（唯一）多项式是什么？这里又是一个富有成效的相互作用与交换代数;最有效的方式来确定多项式涉及syzygies（关系的功能之间的定义地图）;目的是获得快速算法，以确定多项式消失的图像。信息理论的基本问题之一是，信号传输;应用范围从光盘系统的空间通信。在理想情况下，从A点发出的信号和到达B点的信号是相同的。在真实的世界中，传输信号的介质并不完美（存在噪声），因此误差被引入到信号中。在信号处理术语中，传输的信号由码字组成，研究如何清除信号被称为“编码理论”。所以问题很简单：如何捕捉错误？解决方案是在传输中引入一些附加信息，以便B点的接收机可以去除错误并恢复原始信号。事实证明，从某些几何对象获得的代码有时可能是最佳的（即，不需要添加太多冗余信息）。这项提议的一个目的是发现更多这样的代码。该提案的第二个主题涉及计算机视觉和动画。给定一个曲面和空间中的一个点，目标是确定该点是否位于曲面上（例如，在绘制动画电影中角色的图像时会出现这种情况）。如果曲面由方程f（x，y，z）=0和点p=（a，B，c）给出，这很容易做到;只需检查f（a，B，c）是否=0。目标是找到有效的算法来确定f（x，y，z），这通常是未知的。该提案的最后一个主题是研究“样条”，这是波音等公司用来模拟表面的对象。 PI将致力于确定某些对象上样条数量的理论界限，并将分析计算样条的符号代数算法（目前未在该领域使用）的复杂性。实现这两个目标中的任何一个都可能导致用于生成样条曲线的软件的实际速度提高。

This proposal is focused on problems in applied mathematics which may be attacked using algebraic methods. There are three themes: (1) Information transmission and coding theory, (2) Rational surface modeling and implicitization, and (3) Approximation theory and multidimensional splines. The main goal of the project is to bring the full power of abstract machinery to bear on these themes; frequently the key to solving an applied problem is to view it from a different perspective. For example, in past work, the PI has used spectral sequences and local cohomology to study splines; in coding theory the PI has used toric geometry and Cayley-Bacharach theory to obtain good bounds on certain codes obtained from algebraic geometry. The coding theory portion of the project will focus on finding optimal codes from toric varieties of dimension three or more; on the spline front the PI will investigate splines on polyhedral complexes, as well as the efficacy of the Groebner basis algorithm as a symbolic algebra front end for spline computations. Finally, an exciting new interaction between computer science (specifically, computer vision and animation) and algebra involves rational surface modeling: if a map is defined from the plane to three-space by three rational functions, what is the (unique) polynomial vanishing on the image? Here there is again a fruitful interplay with commutative algebra; the most efficient way to determine the polynomial involves syzygies (relations among the functions which define the map); the aim is to obtain fast algorithms to determine the polynomial vanishing on the image.One of the fundamental problems in information theory is that of signal transmission; applications range from CD systems to space communication. In a perfect world, the signal sent from point A and the signal which arrives at point B are identical. In the real world, the medium over which the signal is transmitted is not perfect (there is noise), and so errors are introduced into the signal. In signal processing jargon, the transmitted signal consists of code words, and the study of how to clean up the signal is called ``coding theory''. So the problem is simple: how does one catch the errors? The solution is to introduce some additional information into the transmission, so that the receiver at point B can strip off the errors and recover the original signal. It turns out that codes which are obtained from certain geometric objects can sometimes be optimal (that is, not too much redundant information needs to be added). One aim of this proposal is to discover more such codes. A second theme of the proposal involves computer vision and animation. Given a surface and a point in space, the goal is to decide if the point lies on the surface (this arises, for example, in plotting the image of a character in an animated movie). This is easy to do if the surface is given by an equation f(x,y,z)=0 and the point p=(a,b,c); simply check if f(a,b,c)=0. The goal is to find efficient algorithms to determine f(x,y,z), which is typically unknown. The final theme of the proposal is to study ``splines'', which are objects used by companies like Boeing to model surfaces. The PI will work to determine theoretical bounds on the number of splines on certain objects and will also analyze the complexity of a symbolic algebra algorithm (not currently used in the area) for computing splines. Accomplishing either of these goals could lead to an actual speed up in the software used to generate splines.