文章基本信息

标题：The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk)
本地全文：下载
作者：Micha Sharir
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：77
页码：2:1-2:1
DOI：10.4230/LIPIcs.SoCG.2017.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：For the past 10 years, combinatorial geometry (and to some extent, computational geometry too) has gone through a dramatic revolution, due to the infusion of techniques from algebraic geometry and algebra that have proven effective in solving a variety of hard problems that were thought to be unreachable with more traditional techniques. The new era has begun with two groundbreaking papers of Guth and Katz, the second of which has (almost completely) solved the distinct distances problem of Erdos, open since 1946. In this talk I will survey some of the progress that has been made since then, including a variety of problems on distinct and repeated distances and other configurations, on incidences between points and lines, curves, and surfaces in two, three, and higher dimensions, on polynomials vanishing on Cartesian products with applications, on cycle elimination for lines and triangles in three dimensions, on range searching with semialgebraic sets, and I will most certainly run out of time while doing so.
关键词：Combinatorial Geometry; Incidences; Polynomial method; Algebraic Geometry; Distances