Roel Apfelbaum (TAU) - Public lecture on thesis results - Abstract
============================================================

Title: Geometric Incidences and Repeated Configurations

We give several improved upper and lower bounds on combinatorial-geometric
problems of Incidences and Repeated Configurations:

1) Point-plane incidences: We show that if $n$ points and $m$ planes in $R^3$
   have a large number of incidences (which are simply pairs of point-plane
   such that the point lies on the plane) between them, then there exists a
   large subset of $r$ points together with a large subset of $s$ planes, such
   that each of the $r$ points lies on each of the $s$ planes.
   We provide tight bounds on the magnitude of $rs$ as a function of
   $n$, $m$, and the number of incidences $I$. We also extend these results
   to higher dimensions.

2) Unit area triangles: Given $n$ points in the plane, how many triples of
   points that span a triangle of area 1 can there be?
   Erdos and Purdy ('71) showed that a properly scaled grid of
   $(log n)^{1/2}$ by $n/(log n)^{1/2}$ points spans $\Omega(n^2 log log n)$
   unit area triangles.
   We improve the previously known upper bound (Dumitrescu et al. 2009) and
   show that no $n$ point set can span more than $O(n^{9/4))$ unit area
   triangles.

3) Nondegenerate spheres: In $R^3$, given a finite set of points $P$, a
   sphere $S$, and some global parameter $0 < eta < 1$, we say that $S$ is
   *nondegenerate* with respect to $P$, if for any circle $C$ on $S$, we
   have $|C \cap P| < eta|S \cap P|$, that is, no circle on $S$ contains more
   than an eta-fraction of the incidences of $S$ with $P$.
   We show that given an $n$ point set $P$, the number of nondegenerate
   spheres that contain at least $k$ points of $P$ is at most
   $O(n^(4+\epsilon)/k^{11/2} + n^2/k^2)$, for any epsilon > 0.

4) Repeated similar simplices: Given an $n$ point set $P$ in $R^d$ and a
   $k$-dimensional simplex $\Delta$, how many $(k+1)$-tuples of points of $P$
   can there be that span a simplex similar (i.e., proportional) to $\Delta$?
   We provide upper bounds on this number for various values of $d$ and $k$.
   For $d=3$ and $k=2$, i.e., for similar triangles in $R^3$, we show that for
   any set $P$ of $n$ points, and for any triangle $Delta$, the number of
   triagnles similar to $Delta$ whose vertices belong to $P$ is at most
   $O(n{58/27 + epsilon})$, for any epsilon > 0.
   For general $d$ and $k=d-1$, or $k=d-2$, we show that the number of
   similar simplices is $O(n{d-2 + epsilon})$, where epsilon decays
   exponentially with $d$ (cf. the naive bound is $O(n^{k+1})$ simplices).

Joint work with Pankaj Agarwal, George Purdy and Micha Sharir.