Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
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)
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!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login