Surface modeling, approximation theory, and coding theory

这一建议的重点是应用数学中的问题，这些问题可以用代数方法来解决。有三个主题：(1)信息传递与编码理论；(2)有理面建模与隐式化；(3)逼近理论与多维样条。该项目的主要目标是将抽象机器的全部力量用于这些主题；通常，解决一个实际问题的关键是从不同的角度来看待它。例如，在过去的工作中，PI使用谱序列和局部上同调来研究样条；在编码理论中，PI利用环面几何和Cayley-Bacharach理论得到了代数几何中某些码的良好界。项目的编码理论部分将侧重于从三维或更多维度的环变中寻找最优编码；在样条前端，PI将研究多面体复合体上的样条，以及Groebner基算法作为样条计算的符号代数前端的有效性。最后，计算机科学（特别是计算机视觉和动画）和代数之间令人兴奋的新互动涉及到有理面建模：如果一个映射由三个有理函数从平面到三维空间定义，那么在图像上消失的（唯一的）多项式是什么？这里又与交换代数有了很好的相互作用；确定多项式的最有效方法涉及到协同（定义映射的函数之间的关系）；目的是获得快速确定多项式在图像上消失的算法。信息论的一个基本问题是信号传输问题；应用范围从CD系统到空间通信。在一个完美的世界里，从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.