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

点击翻译按钮获取中文摘要

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