Surface modeling, approximation theory, and coding theory

表面建模、近似理论和编码理论

• 批准号: 0707667
• 负责人: Henry Schenck
• 金额: $ 6.58万
• 依托单位: Texas A&M Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-15 至 2008-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0707667&HistoricalAwards=false
• 关键词: Surface; modeling; approximation; theory; coding

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.

这项建议的重点是应用数学中的问题，这些问题可能会被代数方法攻击。其中包括三个主题：(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将致力于确定某些对象上样条线数量的理论界限，并将分析用于计算样条线的符号代数算法(目前未在该区域使用)的复杂性。实现这两个目标中的任何一个都可能导致用于生成样条线的软件的实际速度加快。