 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, September 19, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Micha Sharir (Tel Aviv University)

## Recent progress on incidences and distinct distances: Variants of the Elekes-Ronyai problem

Consider the following scenario, related to studies by Elekes and Ronyai and by Elekes and Szabo. Let A,B,C be three sets of n real numbers each, let z=f(x,y) be a bivariate polynomial, and let M denote the number of points (x,y,z) of A x B x C at which z=f(x,y). It was shown that if M=Ω(n1.95) then f must be of one of the special forms p(q(x)+r(y)) or p(q(x)r(y)), for suitable polynomials p,q,r.

We present a different approach to the problem, and `almost' get an alternative proof, improving, in doing so, the threshold on M to O(n11/6).

Instead of closing the gap in the general alternative proof, which is still open for us, we consider several concrete problems that fit into this framework, where the gap in the analysis can be closed, and we get improved bounds (and simpler proofs).

Two of the problems that we consider are:

(i) Let p1, p2, p3 be three non-collinear points in the plane, and let P be a set of n other points in the plane. We show that the number of distinct distances between p1,p2,p3 and the points of P is Ω(n6/11), improving an earlier upper bound of Ω(n0.502) of Elekes and Szabo. (This problem was initiated by Erdos, Lovasz and Vesztergombi.)

(ii) Let L1, L2 be two lines in the plane which are neither parallel nor orthogonal, let P1 be a set of m points on L1, and let P2 be a set of n points on L2. We show that the number of distinct distances between P1 and P2 is Ω(\min \{ m2/3n2/3, m2, n2 \}), improving an earlier bound by Elekes. (This problem was initiated by Purdy.)

Joint work with A. Sheffer, J. Solymosi, and others.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks