Distinct Distances on Algebraic Curves in the Plane

Let S be a set of n points in R-2 contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by S is at least c(d)n(4/3), unless C contains a line or a circle. We also prove the lower bound c(d)' min{m(2/3)n(2/3), m(2), n(2)} for the number of distinct distances between m points on one irreducible plane algebraic curve and n points on another, unless the two curves are parallel lines, orthogonal lines, or concentric circles. This generalizes a result on distances between lines of Sharir, Sheffer and Solymosi in [19].

Few distinct distances implies no heavy lines or circles

Frank de Zeeuw

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set of n points determines o(n) distinct distances, then no line contains Omega(n (7/8)) points of and no circle contains Omega(n (5/6)) points of . We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20]. A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.

Springer Heidelberg2016

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

The present thesis deals with problems arising from discrete mathematics, whose proofs make use of tools from algebraic geometry and topology. The thesis is based on four papers that I have co-authored, three of which have been published in journals, and one has been submitted for publication (and also appeared as a preprint on the arxiv, and as an extendend abstract in a conference). Specifically, we deal with the following four problems: \begin{enumerate} \item We prove that if

M\in \mathbb{C}^{2\times2}

is an invertible matrix, and

B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}

is a bilinear form

B_M(p,q)=p^TMq

, then any finite set

S

contained in an irreducible algebraic curve

C

of degree

d

\mathbb{C}^2

determines

\Omega_d(|S|^{4/3})

distinct values of

B_M

, unless

C

is a line, or is linearly equivalent to a curve defined by an equation of the form

x^k=y^l

, with

k,l\in\mathbb{Z}\backslash\\{0\\}

, and

\gcd(k,l)=1

. \item We show that if we are given

m

points and

n

lines in the plane, then the number of distinct distances between the points and the lines is

\Omega(m^{1/5}n^{3/5})

, as long as

m^{1/2}\le n\le m^2

. Also, we show that if we are given

m

points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is

\Omega(m^{4/3})

. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound

\Omega(|S|^4)

on the number of ordinary conics determined by a finite point set

S

\mathbb{R}^2

, assuming that

S

is not contained in a conic, and at most

c|S|

points of

S

lie on the same line (for some $0

EPFL2017