AF: Small: Exploring Algebraic Methods in Computational and Combinatorial Geometry

AF：小：探索计算和组合几何中的代数方法

• 批准号: 1218791
• 负责人: Boris Aronov
• 金额: $ 34.83万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218791&HistoricalAwards=false
• 关键词: AF; Small; Exploring; Algebraic; Methods

Building on recent progress in applying algebraic methods to traditional problems of computational and combinatorial geometry, the PI will explore further use of the tools of algebraic geometry in this subject. In particular, the PI will develop novel algebraic techniques-- as an alternative to random sampling,-- for addressing geometric incidence problems,-- for tackling range searching questions,-- for making progress on the problem of repeated distances in the plane, and-- to facilitate multilevel partitioning schemes, by extending the ideas of Guth and Katz, and of Sharir and co-authors, combining algebraic tools such as Bezout's theorem, fast Fourier transform, and Veronese lifting with existing methods from computational and combinatorial geometry.This work will significantly expand the arsenal of tools available to researchers in computational and combinatorial geometry. The techniques of this field, in turn, have wide-ranging applications in a variety of practical subjects, such as computer graphics, geographic information systems, machine learning, and robotics path planning, amongst others.PI's home institution (Polytechnic Institute of NYU) has historically had a very diverse student body. Education is much more effective when in the classroom students encounter easily accessible research problems that remain open to this day. Such problems have been and will be discussed in computational geometry and algorithms courses taught by PI, increasing accessibility and public appreciation of the somewhat nebulous "research in theoretical computer science."

在将代数方法应用于传统计算几何和组合几何问题的最新进展的基础上，PI将进一步探索代数几何工具在这一学科中的使用。特别是，PI将开发新的代数技术--作为随机抽样的替代方案--用于解决几何关联问题，-用于解决范围搜索问题--用于在平面内重复距离的问题上取得进展，以及-通过扩展Guth和Katz以及Sharir和合著者的想法来促进多级划分方案，将诸如Bezout定理、快速傅立叶变换和Veronese提升等代数工具与计算和组合几何的现有方法相结合。这项工作将显著扩大计算和组合几何研究人员可用的工具库。这一领域的技术反过来在各种实用学科中有广泛的应用，如计算机图形学、地理信息系统、机器学习和机器人路径规划等。国际学生联合会的母校(纽约大学理工学院)历来有非常多样化的学生群体。当学生在课堂上遇到容易理解的研究问题时，教育就会更有效，这些问题至今仍未解决。这些问题已经并将在PI教授的计算几何和算法课程中讨论，这增加了人们对有些模糊的“理论计算机科学研究”的可及性和公众欣赏。