License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.2
URN: urn:nbn:de:0030-drops-72384
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7238/
Go to the corresponding LIPIcs Volume Portal

Sharir, Micha

The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk)

pdf-format:
LIPIcs-SoCG-2017-2.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{sharir:LIPIcs:2017:7238,
  author =	{Micha Sharir},
  title =	{{The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk)}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7238},
  URN =		{urn:nbn:de:0030-drops-72384},
  doi =		{10.4230/LIPIcs.SoCG.2017.2},
  annote =	{Keywords: Combinatorial Geometry, Incidences, Polynomial method, Algebraic Geometry, Distances}
}

Keywords: Combinatorial Geometry, Incidences, Polynomial method, Algebraic Geometry, Distances
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI