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将有效地确定某些对象上的花样数量的理论界限，还将分析用于计算花样的符号代数算法的复杂性（当前在该区域中未使用）。实现这两个目标都可能导致用于生成花样的软件中的实际速度。