Search

This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$. A set of points $P$ is \emph{$k$-blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked set has bounded size (as a function of $k$). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$-th colour class. Amongst other results, for infinitely many values of $k$, we construct $k$-blocked sets with $k^{1.79...}$ points.

This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane.

We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$, every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of K\'ara, P\'or, and Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].

For a set of distances D={d_1,...,d_k} a set A is called D-avoiding if no pair of points of A is at distance d_i for some i. We show that the density of A is exponentially small in k provided the ratios d_1/d_2, d_2/d_3, ..., d_{k-1}/d_k are all small enough. This resolves a question of Szekely, and generalizes a theorem of Furstenberg-Katznelson-Weiss, Falconer-Marstrand, and Bourgain. Several more results on D-avoiding sets are presented., Comment: 23 pages, 3 figures, typos and small errors fixed