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

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

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."