Interval analysis, computer graphics algorithms and social networks

区间分析、计算机图形算法和社交网络

• 批准号: 8081-2013
• 负责人: Rokne, Jon
• 金额: $ 1.09万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568554
• 关键词: Interval; analysis; computer; graphics; algorithms

Interval analysis uses real compact intervals for algorithm development as opposed to real numbers. This enables the inclusion of both computational and experimental error in the computations and to develop algorithms that deliver guaranteed result within intervals. In this area it is proposed to continue the work on devising efficient methods for the range of functions using interval analysis techniques. The result of this investigation will be applied to the interval Newton method, the interval generalization of Newton's method in numerical analysis for the solution of non-linear equations. It is also proposed to investigate the degree elevation and reduction of interval Bezier curves and surfaces. These curves and surfaces are interval generalizations of the commonly used Bezier curves and surfaces in computer graphics. They based on the interval Bernstein polynomials first investigated by the PI. When Bernstein polynomials are degree elevated and reduced the error committed in the computations means that the polynomial degree is no longer correct. In computer graphics, it is proposed to continue the work on rendering efficiency in particular on GPU's. A sophisticated indexing scheme will be considered that avoid superfluous computations. In computational geometry, the work on efficient intersections for 3D solids will be continued. This work is of importance for several areas which involve geometric computations such as for example computer graphics, GIS and solid modeling, This work used techniques from interval analysis combined with exact computation tools. Applied problems in social networks will be considered as they pertain to local industry needs. In particular the work with a local company on a scheme for charitable donations has been successful. Support for this project was provided by MITACS and will be applied for from MITACS for the next phase. A local company that is a world class leader in crowdsourcing is developing an expanded system for which they need expert advise and implementation assistance. An application by the PI and a colleague for MITACS support is currently being considered.

区间分析使用真实的紧凑区间进行算法开发，而不是使用真实的数字。这使得在计算中包括计算和实验误差，并开发在间隔内提供保证结果的算法。在这一领域，建议继续开展工作，利用区间分析技术为各种函数设计有效的方法。本文的研究结果将应用于区间牛顿法，即数值分析中求解非线性方程组的牛顿法的区间推广。 还提出研究区间Bezier曲线和曲面的升阶和降阶问题。这些曲线和曲面是计算机图形学中常用的Bezier曲线和曲面的区间推广。 他们的基础上的间隔伯恩斯坦多项式首先调查的PI。当伯恩斯坦多项式的次数被提高和降低时，计算中犯的错误意味着多项式次数不再正确。在计算机图形学中，有人建议继续在渲染效率方面的工作，特别是在GPU上。将考虑一个复杂的索引方案，以避免多余的计算。在计算几何中，将继续进行三维实体有效相交的工作。这项工作是重要的几个领域，涉及几何计算，例如计算机图形学，地理信息系统和实体建模，这项工作使用的技术，从区间分析结合精确的计算工具。社交网络中的应用问题将被考虑，因为它们与当地行业的需求有关。特别是，与当地一家公司就慈善捐款计划开展的工作取得了成功。该项目由MITACS提供支持，下一阶段将向MITACS申请支持。当地一家在众包领域处于世界领先地位的公司正在开发一个扩展系统，他们需要专家建议和实施援助。PI和一位同事申请MITACS支持，目前正在考虑中。