Month: October 2019

by

Incidences: Open Problems (part 2)

We now continue our journey of seeing how we still don’t know much about geometric incidences. So far, we looked at two main problems concerning incidences with curves in the plane (see the first post of the series). It might make sense to move to study incidences in higher dimensions. Instead, we are now regressing to discuss a problem about incidences with lines in the plane.

Problem 3. Structure for point-line incidences.

The exact asymptotic bound for point-line incidences in {\mathbb R}^2 was derived in the early 1980’s. Although several decades have passed, we still know relatively little about the point-line configurations that lead to many incidences. This is the structural problem: characterizing the point-line configurations that achieve the asymptotically maximal number of incidences.

It is not surprising that we do not know much about the structural problem, since this is the case for most problems in this part of discrete geometry – even after the extremal bound is obtained, we are not able say much about the structure of the extremal solutions. The major exception that comes to mind is the Green-Tao structural result for ordinary lines.

Back to point-line incidences in {\mathbb R}^2 , consider the case of n points and n lines. The Szemerédi–Trotter theorem states that the maximum number of incidences in this case is \Theta(n^{4/3}) . We have two constructions that achieve this bound: The original construction of Erdős and a simplified construction by Elekes. The points of the first construction are a \sqrt{n}\times \sqrt{n} section of the integer lattice {\mathbb Z}^2 . The points in the second construction are an n^{1/3}\times n^{2/3} section of {\mathbb Z}^2 (see figure below). One can further play with these constructions by applying projective transformations and taking subsets of the lattice.

ElekConst

Here are some structural question one might ask about point-line configurations with \Theta(n^{4/3}) incidences:

  • Are \sqrt{n}\times \sqrt{n} and n^{1/3}\times n^{2/3} the only lattice sizes that can achieve \Theta(n^{4/3}) incidences? For example, can we use an n^{2/5}\times n^{3/5} section of {\mathbb Z}^2 ? Is there a continuous spectrum of lattice sizes or are there only a few sporadic sizes?
  • Must there always be a line that contains \sqrt{n} of the points? (not necessarily a line from the set of n lines). It is easy to show that there must exist a line containing n^{1/3} points. I am not aware of any stronger bound for this problem.
  • Must we rely on a section of {\mathbb Z}^2 ? (possibly with a projective transformation and removing some points) Are there other lattices that work? Are there constructions that do not come from lattices?

Continue reading →

by

New Horizons in Geometry and Micha Sharir

Always wanted to visit Israel? Like discrete or computational geometry, and Micha Sharir? Considering what to do with this year’s travel funds? Join us in Tel Aviv!

https://geometrynyc.wixsite.com/sharir (Open on a computer – does not support mobile yet.) If you can, please help us spread the word.

Micha

Partial list of speakers:

  • Pankaj Agarwal (Duke)
  • Noga Alon (Princeton)
  • Boris Aronov (NYU)
  • Shiri Artstein-Avidan (Tel Aviv University)
  • Kenneth Clarkson (IBM Almaden Research center)
  • Herbert Edelsbrunner (IST Austria)
  • Esther Ezra (Bar Ilan University)
  • Leonidas Guibas (Stanford)
  • Dan Halperin (Tel Aviv University)
  • Sariel Har-Peled (University of Illinois at Urbana–Champaign)
  • Gil Kalai (Hebrew University of Jerusalem)
  • Haim Kaplan (Tel Aviv University)
  • Nets Katz (Caltech)
  • Matya Katz (Ben Gurion University)
  • Klara Kedem (Ben Gurion University)
  • Nati Linial (Hebrew University of Jerusalem)
  • Janos Pach (Alfréd Rényi Institute of Mathematics)
  • József Solymosi (UBC)
  • Emo Welzl (ETH Zurich)

The conference is organized by Orit Raz, Natan Rubin, and myself. But the nice list of speakers is not due to us – Micha has a lot of impressive friends!

For any questions about the conference, feel free to contact me.